Mini-Challenge Beschreibung

Daten und Libraries

library(tidyverse)
Registered S3 methods overwritten by 'dbplyr':
  method         from
  print.tbl_lazy     
  print.tbl_sql      
── Attaching packages ───────────────────────────────────────────────────────────────────────────────────────────────── tidyverse 1.3.2 ──✔ ggplot2 3.4.0      ✔ purrr   0.3.5 
✔ tibble  3.1.8      ✔ dplyr   1.0.10
✔ tidyr   1.2.1      ✔ stringr 1.5.0 
✔ readr   2.1.3      ✔ forcats 0.5.2 ── Conflicts ──────────────────────────────────────────────────────────────────────────────────────────────────── tidyverse_conflicts() ──
✖ dplyr::filter() masks stats::filter()
✖ dplyr::lag()    masks stats::lag()
library(recommenderlab)
Loading required package: Matrix

Attaching package: ‘Matrix’

The following objects are masked from ‘package:tidyr’:

    expand, pack, unpack

Loading required package: arules

Attaching package: ‘arules’

The following object is masked from ‘package:dplyr’:

    recode

The following objects are masked from ‘package:base’:

    abbreviate, write

Loading required package: proxy

Attaching package: ‘proxy’

The following object is masked from ‘package:Matrix’:

    as.matrix

The following objects are masked from ‘package:stats’:

    as.dist, dist

The following object is masked from ‘package:base’:

    as.matrix

Loading required package: registry
library(gridExtra)

Attaching package: ‘gridExtra’

The following object is masked from ‘package:dplyr’:

    combine

Daten einlesen

data(MovieLense)

Beim Einlesen des Datensatzes werden drei realRatingMatrix eingelesen: MovieLense, MovieLenseMeta und MovieLenseUser. Wir untersuchen nun zuerst MovieLense.

Library Methoden zum Datensatz MovieLense

methods(class = class(MovieLense))
 [1] [                      [<-                    binarize               calcPredictionAccuracy coerce                 colCounts             
 [7] colMeans               colSds                 colSums                denormalize            dim                    dimnames              
[13] dimnames<-             dissimilarity          evaluationScheme       getData.frame          getList                getNormalize          
[19] getRatingMatrix        getRatings             getTopNLists           hasRating              image                  normalize             
[25] nratings               Recommender            removeKnownRatings     rowCounts              rowMeans               rowSds                
[31] rowSums                sample                 show                   similarity            
see '?methods' for accessing help and source code

Diese Übersicht zeigt uns, welche Methoden mit der realRatingMatrix in Kombination mit Recommenderlab möglich sind.

MovieLense Dataframe erstellen

MovieLenseEDA <- as(MovieLense, "data.frame")

Um den EDA-Teil lösen zu können, haben wir die realRatingMatrix in einen data.frame umgewandelt.

Kopfzeile und Fusszeile vom Datensatz ausgeben

head(MovieLenseEDA)

tail(MovieLenseEDA)

Um eine Idee der Daten zu erhalten, haben wir den Head und Tail des Dataframes ausgegeben. Es wird ersichtlich, dass für jede Zeile ein User, Item (Film) und das Rating erfasst sind.

Infos zum Datensatz

summary(MovieLenseEDA)
     user               item               rating    
 Length:99392       Length:99392       Min.   :1.00  
 Class :character   Class :character   1st Qu.:3.00  
 Mode  :character   Mode  :character   Median :4.00  
                                       Mean   :3.53  
                                       3rd Qu.:4.00  
                                       Max.   :5.00  

Mit der Summary Funktion haben wir uns einen Überblick über die Zahlen im Datensatz erschaffen. Es sind jeweils 99’392 User und Items erfasst. Die Ratings reichen vom Bereich 1 bis 5 und der Mittelwert beträgt 3.53 (Median 4.0)

1 Explorative Datenanalyse

Aufgabe 1: Untersuche den vollständigen MovieLense Datensatz (d.h. vor Datenreduktion!) und beantworte folgende Fragen:

1.1 Welches sind die am häufigsten geschauten Genres/Filme?

1.1.1 Welches sind die am häufigsten geschauten Filme?

MovieLenseEDA %>% 
  group_by(item) %>% 
  summarise(Anzahl = n()) %>%
  arrange(desc(Anzahl)) %>% 
  head(n=10)

Diese Tabelle zeigt uns die Top-10 der am meisten geschauten, resp. gerateten Filme. Es wird ersichtlich, dass Star Wars (1977, vermutlich “Krieg der Sterne”) 583 mal geschaut und geratet wurde.

1.1.2 Welches sind die am häufigsten geschauten Genre?

# Full Join mit df_movies_rating und MovieLenseMeta
MovieLenseEDA_Joined <- full_join(MovieLenseEDA, MovieLenseMeta, 
          by = c("item" = "title")) %>% 
  select(-c("user", "item", "rating", "year", "url")) 

# Aufsummieren der Genre Spalten
(colSums(MovieLenseEDA_Joined)) %>% sort(decreasing = TRUE)
      Drama      Comedy      Action    Thriller     Romance   Adventure      Sci-Fi         War       Crime  Children's      Horror     Mystery 
      39446       29778       25510       21808       19203       13688       12694        9398        8027        7143        5280        5237 
    Musical   Animation     Western   Film-Noir     Fantasy Documentary     unknown 
       4954        3605        1854        1733        1352         758          10 

Wir erkennen, dass das am häufigsten geschauten Genre “Drama” mit 39’446 Ratings ist. Auf dem zweiten Platz befindet sich “Comdey” und auf dem dritten “Action”. Am wenigsten häufig wurden “Documentary” und “unknown” geschaut.

1.2 Wie verteilen sich die Kundenratings gesamthaft und nach Genres?

# DataFrame join
MovieLenseEDA_Joined <- full_join(MovieLenseEDA, MovieLenseMeta, 
          by = c("item" = "title"))

Für diese Frage haben wir einen neuen Datensatz “MovieLenseEDA_Joined” erstellt. Er ergibt sich aus MovieLenseEDA und MovieLenseMeta. Folgend nun die Beantwortund der Frage.

1.2.1 Verteilung der Kundenratings Gesamthaft

MovieLenseEDA_Joined$rating <- as.factor(MovieLenseEDA_Joined$rating)

# Dataframe Uebersicht
MovieLenseEDA_Joined %>% group_by(rating) %>%
  summarize(Anzahl = n())

# Visuelle Darstellung mittels Barplot
MovieLenseEDA_Joined %>% group_by(rating) %>%
  summarize(Anzahl = n()) %>% 
  ggplot(aes(x = rating, y = Anzahl)) + 
  geom_bar(stat = "identity", 
           fill = "lightblue", 
           color = "black") + 
  labs(x = "Ratings", 
       y = "Anzahl", 
       title = "Verteilung der Kundenratings Gesamthaft",
       subtitle = paste("Gesamte Anzahl Kundenratings:", dim(MovieLenseEDA_Joined)[1]))

Wie wir in im Dataframe sowie im Barplot erkennen, werden am häufigsten die Ratings 3 und 4 vergeben. Rating von 1 und 2 kommen deutlich weniger vor, als möglicher Grund könnte sein, dass Filme die schlecht sind gar nicht bewertet wurden, da man sich nicht mehr weiter mit schlechten Filmen befassen möchte. Aus eigenen Erfahrungen können wir sagen, dass man eher mehr bereit ist einen Film zu bewerten, wenn diese auch wirklich gut ist. Das Rating 5 kommt am dritthäufigsten vor.

1.2.2 Verteilung der Kundenratings nach Genre

MovieLenseEDA_Joined$rating <- as.integer(MovieLenseEDA_Joined$rating)

MovieLenseEDA_Joined %>% 
  select(-c("item", "user", "year", "url")) %>% 
  pivot_longer(cols=c("unknown", "Action", "Adventure", "Animation", "Children's",
                      "Comedy", "Crime", "Documentary", "Drama", "Fantasy",
                      "Film-Noir", "Horror", "Musical", "Mystery", "Horror",
                      "Musical", "Mystery", "Romance", "Sci-Fi", "Thriller",
                      "War", "Western"),
               names_to = "Genre", values_to = "is_genre") %>%
  filter(is_genre == 1) %>% 
  ggplot(aes(x = rating)) +
  geom_bar(fill = "lightblue", color = "black") +
  labs(x = "Ratings", 
       y = "Anzahl", 
       title = "Verteilung der Kundenratings nach Genre",
       subtitle = paste("Gesamte Anzahl Kundenratings:", dim(MovieLenseEDA_Joined)[1])) + 
  facet_wrap(~Genre)

In der Visualisierung der Verteilung der Kundenratings pro Genre erkennen wir analog, wie bei der Verteilung der gesamthaften Kundenratings, dass die Rating 3 und 4 am meisten vergeben werden. Dieses Muster ist bei fast allen Genres erkennbar, einfach mit unterschiedlicher Intensität (Anzahl Ratings).

1.3 Wie verteilen sich die mittleren Kundenratings pro Film?

# Dataframe
MovieLenseEDA %>% 
  group_by(item) %>% 
  summarize(mean_rating_per_film = mean(rating),
            n_rating_per_film = n()) %>% 
  arrange(n_rating_per_film)

# Visualisierung
MovieLenseEDA %>% 
  group_by(item) %>% 
  summarize(mean_rating_per_film = mean(rating)) %>% 
  ggplot(aes(x = mean_rating_per_film)) + 
  geom_histogram(color = "black", fill = "lightblue", binwidth = 0.1) +
    labs(x = "Ratings", 
       y = "Anzahl", 
       title = "Verteilung der Mittleren Kundenratings pro Film",
       subtitle = paste("Gesamte Anzahl Kundenratings:", dim(MovieLenseEDA)[1]))

Wir erkennen im Plot die Verteilung durchschnittliche Rating pro Film. Auch hier ist erkennbar, dass die meisten Ratings zwischen 3 und 4 liegen. Einen Ausreisser gibt es beim Rating 1. Bei den natürlichen/ganzzähligen Zahlen erkennen wir ein überraschendes Muster: Die Anzahl erscheint jeweils höher als bei den umliegenden Ratings mit Kommastellen. Dies liegt daran, dass es Filme gibt die nur eine oder wenige Bewertungen bekommen haben (siehe ausgegebenes Datafarme).

1.4 Wie stark streuen die Ratings von individuellen Kunden?

MovieLenseEDA %>% filter(user == c(1:9)) %>% 
  ggplot(aes(x = user, y = rating)) +
  geom_violin(color = "black", fill = "lightblue") +
  labs(x = "User", 
       y = "Ratings", 
       title = "Streueung der Ratings von individuellen Kunden",
       subtitle = "MovieLenseData, Kunden 1-9")

Im Violinenplot stellen wir die ersten 9 User und deren Rating Verteilungen dar. Wir erkennen im Plot, dass User 2 und 8 Filme sehr ähnliche bewerten. Beide bewerten Filme öfters mit einer 4 und eher weniger eine 3 und 5, aber nie 2 und 1. User 5 und 9 bewerten Filme hingegen im ganzen Bereich.

1.5 Welchen Einfluss hat die Normierung der Ratings pro Kunde auf deren Verteilung?

MovieLensenormalized <- normalize(MovieLense)
MovieLenseEDA_Normalized <- (as(MovieLensenormalized, "data.frame"))

MovieLenseEDA_Normalized %>% filter(user == c(1:9)) %>% 
  ggplot(aes(x = user, y = rating)) +
  geom_violin(color = "black", fill = "lightblue") +
  labs(x = "User", 
       y = "Normalisierte Ratings", 
       title = "Normalisierte Streueung der Ratings von individuellen Kunden",
       subtitle = "MovieLenseData, Kunden 1 - 9")

Für die Normierung der Daten haben wir die Funktion von Recommenderlab verwendet. Der Mittelwert der Ratings pro User beträgt nun Null. Im Plot verschiebt sich nun nicht nur die y-Achse, sondern auch die Bandbreite. user 5 und 9, die auf den Rohdaten 1-5 bewertet haben, haben nun unterschiedliche Bandbreiten. Dies liegt daran, dass der Mittelwert der beiden User unterschiedlich ist.

1.6 Welche strukturellen Charakteristika (z.B. Sparsity) und Auffälligkeiten zeigt die User-Item Matrix?

image(x = MovieLense, 
      xlab = "Items", 
      ylab = "Users", 
      main = "Sparisty 943 x 1664 User-Item Matrix 943 x 1664") 


image(MovieLense[1:50,1:50],
      xlab = "Items",
      ylab = "Users", 
      main = "Sparisty 50 x 50 User-Item Matrix")


# nratings(MovieLense) zaehlt die Anzahl vorhandenen Kombinationen von User und Items
(nratings(MovieLense) / (dim(MovieLense)[1] * dim(MovieLense)[2]) * 100)
[1] 6.334122

Für die Darstellung der Sparsity haben wir die image Funktion von Recommenderlab verwendet. Jede Zeile von MovieLense entspricht einem Benutzer und jede Spalte einem Film und für jede geschaute Kombination wird ein Pixel in Graustufen, je nach Rating, markiert. Im ersten Plot wird ersichtlich, dass die ersten User weniger Filme bewertet haben, denn oben rechts sind keine Punkte mehr ersichtlich. Auch ist auffällig, dass die ersten etwa 500 häufiger geschaut wurden, denn bis zu diesem Bereich sind am meisten Pixel eingefärbt. Um die Darstellung genau verstehen zu können, haben wir im zweiten Plot nur die ersten 50 User und Items dargestellt. Dort ist die hohe Sparsity gut erkennbar. Gesamthaft gibt es 943 x 1664 = 1’569’152 Kombinationen zwischen User und Film. Allerdings hat nicht jeder Nutzer jeden Film gesehen, aus diesem Grund ist es wichtig die sparsity der Matrix zu betrachten. In MovieLense Matrix fehlen ca. 94% der Kombinationen. Nur für 6.3% der möglichen Kombinationen sind Ratings vorhanden.

2 Datenreduktion

Aufgabe 2: Reduziere den MovieLense Datensatz auf rund 400 Kunden und 700 Filme, indem du Filme und Kunden mit sehr wenigen Ratings entfernst.

2.1 Vorbereitung

2.1.1 DataFrame neu einlesen

MovieLenseToCut <- as(MovieLense, "data.frame")
MovieLenseToCut

2.1.2 Auswahl der 400 Kunden

select_user_400 <- function(movie_df, start, end) {
  selected_user <- movie_df %>% 
    group_by(user) %>% 
    summarize(Anzahl = n()) %>% 
    arrange(desc(Anzahl)) %>% 
    slice(start:end)
  selected_user
}

MovieLense400User_1 <- select_user_400(MovieLenseToCut, 0, 400)
MovieLense400User_1

MovieLense400User_2 <- select_user_400(MovieLenseToCut, 200, 599)
MovieLense400User_2

Bei der Auswahl der 400 User haben wir direkt auch zwei Dataframes erstellt, da wir die MC zu zweit bearbeiten. Für Person 1 haben wir die 400 User mit den meisten Ratings ausgewählt und für Person 2 User 200 bis 600. Wir haben dieses Vorgehen gewählt um sicherzustellen, dass nur eine Teil der User in beiden Dataframes enthalten ist. Alternativ hätten wir von den Top 500 User zufällig 80% für Person 1 und 2 verwendet, dann hätte die Überlappung aber sehr hoch sein können, so ist es nur die Hälft.

2.1.3 Auswahl der 700 Movies

select_item_700 <- function(movie_df, start, end) {
  selected_item <- MovieLenseToCut %>% 
  group_by(item) %>% 
  summarise(Anzahl = n()) %>% 
  arrange(desc(Anzahl)) %>% 
  slice(start:end)
}

MovieLense700Items_1 <- select_item_700(MovieLenseToCut, 0, 700)
MovieLense700Items_1

MovieLense700Items_2 <- select_item_700(MovieLenseToCut, 150, 849)
MovieLense700Items_2
NA

Das gleiche Vorgehen haben wir bei den Filmen gewählt.

2.1.4 DataFrame schneiden

df_cutter <- function(movie_df, selected_user, selected_items) {
  movie_df_cut <- movie_df %>%
      filter(user %in% c(selected_user$user))
  movie_df_cut <- movie_df_cut %>% 
      filter(item %in% c(selected_items$item))
  movie_df_cut
}

MovieLenseCut_1 <- df_cutter(MovieLenseToCut, MovieLense400User_1, MovieLense700Items_1)
MovieLenseCut_1

MovieLenseCut_2 <- df_cutter(MovieLenseToCut, MovieLense400User_2, MovieLense700Items_2)
MovieLenseCut_2

Untersuche und dokumentiere die Eigenschaften des reduzierten Datensatzes und beschreibe den Effekt der Datenreduktion, d.h.

2.2 Anzahl Filme und Kunden sowie Sparsity vor und nach Datenreduktion,

2.2.1 Vor der Datenreduktion

image(MovieLense, 
      xlab = "Items", 
      ylab = "Users", 
      main = "Vor Datenreduktion, User-Item Matrix 943 x 1664") 


sparsity_text <- function(realrating_matrix) {
  print(paste("Anzahl vorhandene User-Item Rating in", nratings(realrating_matrix) / (dim(realrating_matrix)[1] * dim(realrating_matrix)[2]) * 100, "%"))
  print(paste("Sparsity der Matrix", 100 - (nratings(realrating_matrix) / (dim(realrating_matrix)[1] * dim(realrating_matrix)[2]) * 100), "%"))
}

sparsity_text(MovieLense)
[1] "Anzahl vorhandene User-Item Rating in 6.33412186964679 %"
[1] "Sparsity der Matrix 93.6658781303532 %"

Zur Repetition stellen wir nochmals die Sparsity als Bild dar und berechnen den Wert.

2.2.2 Nach der 1. Datenreduktion

MovieLenseCompact_1 <- as(MovieLenseCut_1, "realRatingMatrix")
image(MovieLenseCompact_1,
      xlab = "Items", 
      ylab = "Users", 
      main = "Nach Datenreduktion 1, User-Item Matrix 400 x 700")


sparsity_text(MovieLenseCompact_1)
[1] "Anzahl vorhandene User-Item Rating in 24.0810714285714 %"
[1] "Sparsity der Matrix 75.9189285714286 %"

Für den ersten Datensatz wird ersichtlich, dass die Ratings gegenüber dem ursprünglichen Datensatz gleichmässig verteilt sind. Vereinzelt sind für User (z.B. im Bereich 90-150) und Items (z.B Bereicht um 600) dunklere Bereiche erkennbar. In diesen dürften die Ratings höher und Sparsity geringer sein. Die Sparsity beträgt nun auch nur noch etwa 75% und für 25% der möglichen Kombinationen zwischen User und Item wurden Ratings angegeben.

Diese starke Änderung war aber zu erwarten, da wir die User und Items mit den meisten Ratings ausgewählt haben.

2.2.3 Nach der 2. Datenreduktion

MovieLenseCompact_2 <- as(MovieLenseCut_2, "realRatingMatrix")
image(MovieLenseCompact_2,
      xlab = "Items", 
      ylab = "Users", 
      main = "Nach Datenreduktion 2, User-Item Matrix 400 x 700")


sparsity_text(MovieLenseCompact_2)
[1] "Anzahl vorhandene User-Item Rating in 6.35142857142857 %"
[1] "Sparsity der Matrix 93.6485714285714 %"

Für den zweiten Datensatz wird ersichtlich, dass die Ratings gegenüber dem ursprünglichen Datensatz gleichmässig verteilt sind, gegenüber dem ersten Datensatz aber sichtbar weniger Ratings vorhanden sind. Dunklere Bereich, wie bei Datensatz1 sind kaum mehr zu erkennen. Die Sparsity beträgt liegt nun bei 93.6%, sie ist gegenüber dem ersten Datensatz also deutlich angestiegen, liegt aber bereits im Bereich des ursprünglichen Wertes. Dieser Anstieg war zu erwarten, da wir nicht mehr die User und Items mit den meisten Ratings ausgewählt haben, sondern z.B. bei den Usern bei Top 200 angefangen haben.

2.3 Mittlere Kundenratings pro Film vor und nach Datenreduktion,

mean_rating_per_film_viz <- function(movie_df) {
  movie_df %>% 
  group_by(item) %>% 
  summarize(mean_rating_per_film = mean(rating)) %>% 
  ggplot(aes(x = mean_rating_per_film)) + 
  geom_histogram(color = "black", fill = "lightblue", binwidth = 0.1) +
    labs(x = "Ratings", 
       y = "Anzahl", 
       title = "Mittlere Kundenratings Verteilung",
       subtitle = paste("Gesamte Anzahl Kundenratings:", dim(movie_df)[1])) +
    geom_vline(xintercept = mean(movie_df$rating), color = "red", linetype = "dashed", size = 0.5)
}
# Vor reduktion
print(mean_rating_per_film_viz(MovieLenseEDA))
Warning: Using `size` aesthetic for lines was deprecated in ggplot2 3.4.0.
Please use `linewidth` instead.

# nach 1. Redutkion
print(mean_rating_per_film_viz(MovieLenseCut_1))

# nach 2. Reduktion
print(mean_rating_per_film_viz(MovieLenseCut_2))

Die erste Visualisierung zeigt den bereits bekannten Plot mit den mittleren Kundenratings für den gesamten Datensatz. Plot 2 und 3 zeigt die selbe Auswertung für die beiden gekürzten Datensätze. In den Visualisierungen erkennen wir, dass der Mittelwert der Kundenrating für den ursprünglichen, sowie auch für die beiden reduzierten Datensätze, nicht grossartig ändert. Die Mittelwerte befinden sich bei allen im Bereich von 3.5. Was aber erkennbar wird, ist, dass bei der 1. Reduktion die hohe Anzahl Rating bei den natürlichen/ganzzahligen Zahlen weggefallen ist. Weiterhin sind bei allen Visualisierungen erkennbar, dass die meisten Rating im Bereich von 3 bis 4 liegen.

2.4 Für Gruppen: Quantifiziere “Intersection over Union” der Ratings der unterschiedlich reduzierten Datensätze.

intersect_join <- inner_join(MovieLenseCut_1, MovieLenseCut_2, by = c("user", "item"))
intersect_join

union_join <- full_join(MovieLenseCut_1, MovieLenseCut_2, by = c("user", "item"))
union_join

paste("Eine Intersection over Union von", dim(intersect_join)[1] / dim(union_join)[1] * 100, "%, zwischen den beiden reduzierten Datensätzen")
[1] "Eine Intersection over Union von 15.5638434935919 %, zwischen den beiden reduzierten Datensätzen"

Zur Beantwortung dieser Frage haben wir einerseits einen Datensatz mit Daten, die in beiden Datensätzen vorhanden sind erstellt und diesen mit der gesamten Anzahl Daten verglichen. Es zeigt sich, dass es eine Überschneidung von 15.6% zwischen den beiden reduzierten Datensätzen gibt. Dieser eher tiefe Wert überrascht, weil z.B. 50% der User übereinstimmen. Aber aufgrund der hohen Sparsity ist die Überschneidung der Daten viel tiefer.

3 Analyse Ähnlichkeitsmatrix

Aufgabe 3: Erzeuge einen IBCF Recommender und analysiere die Ähnlichkeitsmatrix des trainierten Modelles für den reduzierten Datensatz.

3.1 Zerlege den reduzierten MovieLense Datensatz in ein disjunktes Trainings-und Testdatenset im Verhältnis 4:1,

train_test_split <- function(movie_df, split = 0.8) {
  n <- dim(movie_df)[1]
  n_train <- round(n * split)
  n_test <- n - n_train
  training <- movie_df[1:n_train]
  test <- movie_df[(n_train + 1):n]
  return(list(training, test))
}

train_test_list_1 <- train_test_split(MovieLenseCompact_1)
training_1 <- train_test_list_1[[1]]
test_1 <- train_test_list_1[[2]]
training_1
320 x 700 rating matrix of class ‘realRatingMatrix’ with 53971 ratings.
test_1
80 x 700 rating matrix of class ‘realRatingMatrix’ with 13456 ratings.
train_test_list_2 <- train_test_split(MovieLenseCompact_2)
training_2 <- train_test_list_2[[1]]
test_2 <- train_test_list_2[[2]]
training_2
320 x 700 rating matrix of class ‘realRatingMatrix’ with 14368 ratings.
test_2
80 x 700 rating matrix of class ‘realRatingMatrix’ with 3416 ratings.

Beide reduzierten Datensätze wurden im Verhältnis 4:1, (4 Teile Training und 1 Teil Test) reduziert.

3.2 Trainiere ein IBCF Modell mit 30 Nachbarn und Cosine Similarity

ribcf_1 <- Recommender(training_1, "IBCF", param=list(k= 30, method = "cosine"))
ribcf_1
Recommender of type ‘IBCF’ for ‘realRatingMatrix’ 
learned using 320 users.
ribcf_2 <- Recommender(training_2, "IBCF", param=list(k= 30, method = "cosine"))
ribcf_2
Recommender of type ‘IBCF’ for ‘realRatingMatrix’ 
learned using 320 users.

Es wurden jeweils für beide reduzierten Datensaetze ein IBCF Modell mit 30 Nachbarn und der Cosine Similarity mittels der von Recommenderlab zur Verfügung gestellten Methode trainiert. Die Auswertung bestätigt, dass das Training mittels 320 Usern, resp. 80% der ursprünglichen 400, durchgeführt wurde.

3.3 Bestimme die Verteilung der Filme, welche bei IBCF für paarweise Ähnlichkeitsvergleiche verwendet werden

ribcf_sim_item_df <- function(ribcf) {
  # model
  ribcf_model <- getModel(ribcf)
  # dataframe erstellen
  ribcf_sim_df <- as.data.frame(colSums(ribcf_model$sim > 0))
  # Item als neue Spalte hinzufuegen und Index entfernen
  ribcf_sim_df_ <- cbind(item = rownames(ribcf_sim_df), ribcf_sim_df)
  rownames(ribcf_sim_df_) <- NULL
  # return df
  ribcf_sim_df_
}

ribcf_sim_viz <- function(ribcf_sim_df_, n_reduc) {
    ribcf_sim_df_ %>%
    rename(Anzahl = 2) %>% 
    ggplot(aes(x = Anzahl)) + 
    geom_histogram(binwidth =  0.1) +
    labs(title = "Verteilung der Ähnlichkeitsvergleiche",
         x = "Anzahl Filme als Nachbar", 
         y = "Anzahl",
         subtitle = paste("ribcf", n_reduc))
}

ribcf_sim_df_1 <- ribcf_sim_item_df(ribcf_1)
ribcf_sim_viz(ribcf_sim_df_1, 1)


ribcf_sim_df_2 <- ribcf_sim_item_df(ribcf_2)
ribcf_sim_viz(ribcf_sim_df_2, 2)

NA
NA

Im Histogramm erkennt man die Anzahl Filme die als Nachbar bei einem anderen Film auftauchen. Beide Plots sind deutlich unterschiedlich

3.4 Bestimme die Filme, die am häufigsten in der Cosine-Ähnlichkeitsmatrix auftauchen und analysiere deren Vorkommen und Ratings im reduzierten Datensatz.

top_10_item_sim <- function(ribcf_sim_df_, n_reduc) {
  result <- ribcf_sim_df_ %>% 
  rename(Anzahl = 2) %>% 
  arrange(desc(Anzahl)) %>% 
  top_n(10)
    
  print(result)
    
  result %>%   
  ggplot(aes(x = Anzahl, y = item)) +
  # arrange desc
  geom_col(alpha = 0.5, color = "black", fill = "limegreen") +
  labs(title = "Top 10 Filme die am häufigsten in der Nachbarschaft andere Filme auftauchen",
       x = "Anzahl Film als Nachbar", 
       y = "Filme",
       subtitle = paste("ribcf", n_reduc))
}
  
top_10_item_sim(ribcf_sim_df_1, 1)
Selecting by Anzahl

top_10_item_sim(ribcf_sim_df_2, 2)
Selecting by Anzahl

Für jeden der beiden Datensätze haben wir einen Dataframe und Plot mit den Filmen, die am häufigsten in der Cosine-Ähnlichkeitsmatrix auftauchen, erstellt. Bei den top 10 Filmen sind keine Gemeinsamkeiten ersichtlich. Die Anzahl der Vorkommen ist aber ähnlich, der höchste Wert ist zwischen 150 und 160 und die Nummer 10 liegt bei 120 Vorkommen.

4 Implementierung Ähnlichkeitsmatrix

Aufgabe 4 (DIY): Implementiere eine Funktion zur effizienten Berechnung von sparsen Ähnlichkeitsmatrizen für IBCF RS und analysiere die Resultate für 100 zufällig gewählte Filme.

4.1 Implementiere eine Funktion, um (a) für ordinale Ratings effizient

die Cosine Similarity und (b) für binäre Ratings effizient die Jaccard Similarity zu berechnen,

number_user <- 100
number_item <- 100

Diese Variablen haben wir für die Entwicklung der Funktionen verwendet. Wir konnte damit einfach kleinere, z.B. 5, Datensätze slicen.

4.1.1 Cosine Similarity

get_cossim_4 <- function(RatingMatrix, n_user, n_item){
 
  sliced_matrix <- getRatingMatrix(RatingMatrix[1:n_user, 1:n_item])
  
  sliced_matrix_t <- t(sliced_matrix)
  
  temp_sim <- sliced_matrix_t / sqrt(rowSums(sliced_matrix_t ** 2))

  cossim_matrix <- temp_sim %*% t(temp_sim)

  cossim_matrix
}
result_cossim_4 <- get_cossim_4(MovieLense, number_user, number_item)
result_cossim_4[1:20,1:20]
20 x 20 sparse Matrix of class "dgCMatrix"
   [[ suppressing 20 column names ‘Toy Story (1995)’, ‘GoldenEye (1995)’, ‘Four Rooms (1995)’ ... ]]
                                                                                                                                               
Toy Story (1995)                                     1.0000000 0.3786054 0.3557149 0.4085792 0.35406521 0.2106625 0.6507823 0.5128509 0.4809693
GoldenEye (1995)                                     0.3786054 1.0000000 0.1595558 0.4058678 0.33981928 0.1078328 0.2498391 0.2921164 0.2701317
Four Rooms (1995)                                    0.3557149 0.1595558 1.0000000 0.3989039 0.22857516 0.2263010 0.3581228 0.2310704 0.2649610
Get Shorty (1995)                                    0.4085792 0.4058678 0.3989039 1.0000000 0.26745994 0.1328422 0.4245295 0.5445979 0.4781120
Copycat (1995)                                       0.3540652 0.3398193 0.2285752 0.2674599 1.00000000 0.1313064 0.3322003 0.2039381 0.4163740
Shanghai Triad (Yao a yao yao dao waipo qiao) (1995) 0.2106625 0.1078328 0.2263010 0.1328422 0.13130643 1.0000000 0.2130495 0.1805984 0.2092867
Twelve Monkeys (1995)                                0.6507823 0.2498391 0.3581228 0.4245295 0.33220032 0.2130495 1.0000000 0.5179884 0.5991567
Babe (1995)                                          0.5128509 0.2921164 0.2310704 0.5445979 0.20393810 0.1805984 0.5179884 1.0000000 0.6064674
Dead Man Walking (1995)                              0.4809693 0.2701317 0.2649610 0.4781120 0.41637401 0.2092867 0.5991567 0.6064674 1.0000000
Richard III (1995)                                   0.2412952 0.1873510 0.3780578 0.2820925 0.07604487 0.4311379 0.2699059 0.3242348 0.3275021
Seven (Se7en) (1995)                                 0.4553382 0.1632439 0.3843138 0.5195206 0.36995125 0.1093345 0.5694625 0.5399670 0.5360525
Usual Suspects, The (1995)                           0.4651021 0.3486586 0.3794973 0.6074053 0.39453741 0.2776088 0.5844860 0.5715472 0.6633322
Mighty Aphrodite (1995)                              0.5220124 0.2496832 0.3871603 0.3777443 0.19202253 0.3006045 0.5160271 0.4357768 0.4985081
Postino, Il (1994)                                   0.4588155 0.1724141 0.4344255 0.2698077 0.15320397 0.4191717 0.3159025 0.4495279 0.4480904
Mr. Holland's Opus (1995)                            0.6120818 0.2968567 0.3117847 0.3590970 0.39631951 0.1791067 0.5034813 0.3576072 0.5884584
French Twist (Gazon maudit) (1995)                   0.2202742 0.2062550 0.3329636 0.2625611 0.25115377 0.3187884 0.1833778 0.0345436 0.2486767
From Dusk Till Dawn (1996)                           0.3199297 0.3785939 0.2558409 0.3633585 0.32163376 0.2531139 0.2413614 0.2963905 0.3417637
White Balloon, The (1995)                            0.1396962 0.1479453 0.4776651 0.2126344 0.18015094 0.3658636 0.2192261 0.1176950 0.3480472
Antonia's Line (1995)                                0.2946435 0.1047364 0.1690792 0.1032222 0.12753608 0.4662172 0.3078112 0.2350530 0.2710362
Angels and Insects (1995)                            0.1891240 0.1290770 0.4427924 0.1855159 0.15717527 0.4488792 0.1593891 0.2594140 0.3226374
                                                                                                                                                
Toy Story (1995)                                     0.24129522 0.45533821 0.4651021 0.5220124 0.4588155 0.6120818 0.2202742 0.3199297 0.1396962
GoldenEye (1995)                                     0.18735098 0.16324390 0.3486586 0.2496832 0.1724141 0.2968567 0.2062550 0.3785939 0.1479453
Four Rooms (1995)                                    0.37805783 0.38431384 0.3794973 0.3871603 0.4344255 0.3117847 0.3329636 0.2558409 0.4776651
Get Shorty (1995)                                    0.28209250 0.51952065 0.6074053 0.3777443 0.2698077 0.3590970 0.2625611 0.3633585 0.2126344
Copycat (1995)                                       0.07604487 0.36995125 0.3945374 0.1920225 0.1532040 0.3963195 0.2511538 0.3216338 0.1801509
Shanghai Triad (Yao a yao yao dao waipo qiao) (1995) 0.43113793 0.10933445 0.2776088 0.3006045 0.4191717 0.1791067 0.3187884 0.2531139 0.3658636
Twelve Monkeys (1995)                                0.26990593 0.56946246 0.5844860 0.5160271 0.3159025 0.5034813 0.1833778 0.2413614 0.2192261
Babe (1995)                                          0.32423475 0.53996700 0.5715472 0.4357768 0.4495279 0.3576072 0.0345436 0.2963905 0.1176950
Dead Man Walking (1995)                              0.32750209 0.53605254 0.6633322 0.4985081 0.4480904 0.5884584 0.2486767 0.3417637 0.3480472
Richard III (1995)                                   1.00000000 0.35313083 0.3688357 0.3724946 0.4171123 0.1504695 0.1846233 0.3940552 0.4745374
Seven (Se7en) (1995)                                 0.35313083 1.00000000 0.6427527 0.2562351 0.2316937 0.3159148 0.2091273 0.3399173 0.2884724
Usual Suspects, The (1995)                           0.36883567 0.64275270 1.0000000 0.4417965 0.3831814 0.4257209 0.2811128 0.3440000 0.3920784
Mighty Aphrodite (1995)                              0.37249460 0.25623511 0.4417965 1.0000000 0.5845588 0.4709003 0.2874876 0.1293548 0.3692327
Postino, Il (1994)                                   0.41711226 0.23169366 0.3831814 0.5845588 1.0000000 0.4880400 0.2066398 0.2381653 0.5039526
Mr. Holland's Opus (1995)                            0.15046955 0.31591479 0.4257209 0.4709003 0.4880400 1.0000000 0.1586031 0.1868622 0.3185419
French Twist (Gazon maudit) (1995)                   0.18462325 0.20912731 0.2811128 0.2874876 0.2066398 0.1586031 1.0000000 0.2342606 0.4373740
From Dusk Till Dawn (1996)                           0.39405520 0.33991729 0.3440000 0.1293548 0.2381653 0.1868622 0.2342606 1.0000000 0.3360672
White Balloon, The (1995)                            0.47453738 0.28847237 0.3920784 0.3692327 0.5039526 0.3185419 0.4373740 0.3360672 1.0000000
Antonia's Line (1995)                                0.38125745 0.08985732 0.3045318 0.5365988 0.4952783 0.3028259 0.3096346 0.2141239 0.4886175
Angels and Insects (1995)                            0.42364525 0.18246935 0.2980934 0.3282205 0.5172714 0.2431769 0.3815932 0.3420744 0.5303215
                                                                         
Toy Story (1995)                                     0.29464348 0.1891240
GoldenEye (1995)                                     0.10473645 0.1290770
Four Rooms (1995)                                    0.16907917 0.4427924
Get Shorty (1995)                                    0.10322223 0.1855159
Copycat (1995)                                       0.12753608 0.1571753
Shanghai Triad (Yao a yao yao dao waipo qiao) (1995) 0.46621721 0.4488792
Twelve Monkeys (1995)                                0.30781124 0.1593891
Babe (1995)                                          0.23505300 0.2594140
Dead Man Walking (1995)                              0.27103623 0.3226374
Richard III (1995)                                   0.38125745 0.4236452
Seven (Se7en) (1995)                                 0.08985732 0.1824693
Usual Suspects, The (1995)                           0.30453181 0.2980934
Mighty Aphrodite (1995)                              0.53659876 0.3282205
Postino, Il (1994)                                   0.49527834 0.5172714
Mr. Holland's Opus (1995)                            0.30282587 0.2431769
French Twist (Gazon maudit) (1995)                   0.30963462 0.3815932
From Dusk Till Dawn (1996)                           0.21412393 0.3420744
White Balloon, The (1995)                            0.48861751 0.5303215
Antonia's Line (1995)                                1.00000000 0.3100373
Angels and Insects (1995)                            0.31003735 1.0000000

Mit der erstellten Funktion haben wir für den gesamten MovieLense Datensatz die Cosine Similarity Matrix berechnet. Um das Resultat lesbar darzustellen, zeigen wir hier nur die ersten fünf Item. Bei der Analyse der ersten 20 Items wurde ersichtlich, dass die Werte zwischen 0 und 1 liegen. Negative Similarities sind nicht ersichtlich. Wie mit dir besprochen und hergeleitet, ist das aber verständlich, da aufgrund der nicht-negativen Ratings der maximale Winkel 90° beträgt. Hätten wir mit normierten Ratings gearbeitet, wären auch negative Werte aufgetreten.

4.1.2 Jaccard Similarity

get_jaccardsim_4 <- function(RatingMatrix, n_user, n_item){
  
  sliced_matrix_bin <- as(binarize(RatingMatrix[1:n_user, 1:n_item], minRating=4), "matrix")
  
  sliced_matrix_bin_t <- t(sliced_matrix_bin)
  
  matrix_corssprod <- tcrossprod(sliced_matrix_bin_t)
  
  im <- which(matrix_corssprod > 0, arr.ind=TRUE)
  b <- rowSums(sliced_matrix_bin_t)
  Aim <- matrix_corssprod[im]
  
  J = sparseMatrix(
            i = im[,1],
            j = im[,2],
            x = Aim / (b[im[,1]] + b[im[,2]] - Aim),
            dims = dim(matrix_corssprod)
      )
  
  J <- data.matrix(J)
  
  J
}
get_jaccardsim_4(MovieLense, number_user, number_item)
             [,1]       [,2]       [,3]       [,4]       [,5]       [,6]       [,7]       [,8]       [,9]      [,10]      [,11]      [,12]      [,13]
  [1,] 1.00000000 0.05128205 0.05128205 0.13043478 0.10526316 0.07317073 0.38983051 0.31914894 0.24561404 0.04651163 0.22727273 0.25000000 0.17391304
  [2,] 0.05128205 1.00000000 0.00000000 0.06250000 0.00000000 0.00000000 0.02173913 0.03846154 0.02857143 0.00000000 0.00000000 0.03448276 0.00000000
  [3,] 0.05128205 0.00000000 1.00000000 0.06250000 0.00000000 0.12500000 0.06818182 0.00000000 0.05882353 0.11111111 0.05555556 0.07142857 0.11764706
  [4,] 0.13043478 0.06250000 0.06250000 1.00000000 0.12500000 0.00000000 0.20833333 0.31034483 0.23684211 0.10526316 0.30434783 0.32258065 0.15384615
  [5,] 0.10526316 0.00000000 0.00000000 0.12500000 1.00000000 0.00000000 0.06666667 0.07692308 0.12121212 0.00000000 0.11111111 0.10714286 0.05263158
  [6,] 0.07317073 0.00000000 0.12500000 0.00000000 0.00000000 1.00000000 0.08695652 0.07142857 0.08333333 0.18181818 0.04761905 0.10000000 0.10000000
  [7,] 0.38983051 0.02173913 0.06818182 0.20833333 0.06666667 0.08695652 1.00000000 0.28301887 0.32758621 0.08510638 0.27659574 0.39215686 0.20000000
  [8,] 0.31914894 0.03846154 0.00000000 0.31034483 0.07692308 0.07142857 0.28301887 1.00000000 0.39024390 0.14814815 0.29032258 0.34210526 0.17647059
  [9,] 0.24561404 0.02857143 0.05882353 0.23684211 0.12121212 0.08333333 0.32758621 0.39024390 1.00000000 0.14285714 0.28947368 0.46341463 0.19512195
 [10,] 0.04651163 0.00000000 0.11111111 0.10526316 0.00000000 0.18181818 0.08510638 0.14814815 0.14285714 1.00000000 0.15000000 0.13333333 0.09523810
            [,14]      [,15]      [,16]      [,17]      [,18]      [,19]      [,20]      [,21]      [,22]      [,23]      [,24]      [,25]      [,26]
  [1,] 0.19565217 0.27450980 0.05263158 0.05000000 0.02564103 0.10000000 0.02500000 0.00000000 0.23529412 0.22222222 0.06976744 0.24489796 0.05128205
  [2,] 0.00000000 0.07142857 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.07692308 0.00000000 0.00000000 0.04000000 0.00000000
  [3,] 0.11111111 0.07142857 0.25000000 0.00000000 0.66666667 0.12500000 0.20000000 0.00000000 0.07692308 0.11111111 0.10000000 0.13043478 0.00000000
  [4,] 0.10714286 0.10810811 0.06666667 0.05882353 0.06666667 0.00000000 0.06250000 0.07142857 0.30000000 0.14814815 0.22222222 0.08823529 0.06250000
  [5,] 0.00000000 0.10714286 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.03571429 0.05000000 0.00000000 0.08000000 0.16666667
  [6,] 0.15000000 0.06451613 0.14285714 0.11111111 0.14285714 0.20000000 0.28571429 0.00000000 0.10714286 0.21052632 0.00000000 0.07407407 0.28571429
  [7,] 0.10909091 0.24561404 0.04545455 0.02127660 0.04545455 0.11111111 0.04444444 0.00000000 0.27777778 0.19607843 0.10638298 0.24074074 0.02173913
  [8,] 0.28125000 0.13333333 0.00000000 0.03703704 0.00000000 0.07142857 0.08000000 0.00000000 0.28947368 0.24242424 0.10344828 0.14634146 0.12500000
  [9,] 0.21951220 0.33333333 0.06060606 0.05714286 0.06060606 0.08333333 0.09090909 0.00000000 0.28888889 0.28205128 0.07894737 0.21739130 0.09090909
 [10,] 0.20000000 0.03030303 0.00000000 0.10000000 0.12500000 0.08333333 0.11111111 0.00000000 0.14285714 0.14285714 0.07142857 0.11111111 0.11111111
            [,27]      [,28]      [,29]      [,30]      [,31]      [,32]      [,33] [,34]      [,35] [,36] [,37]      [,38]      [,39]      [,40]
  [1,] 0.00000000 0.32653061 0.02631579 0.00000000 0.18604651 0.13636364 0.05000000     0 0.02631579     0     0 0.02564103 0.05000000 0.05263158
  [2,] 0.16666667 0.07142857 0.00000000 0.00000000 0.06666667 0.00000000 0.00000000     0 0.00000000     0     0 0.66666667 0.00000000 0.00000000
  [3,] 0.00000000 0.07142857 0.00000000 0.20000000 0.00000000 0.15384615 0.16666667     0 0.00000000     0     0 0.00000000 0.40000000 0.00000000
  [4,] 0.12500000 0.20588235 0.00000000 0.06250000 0.17391304 0.23809524 0.12500000     0 0.00000000     0     0 0.06666667 0.20000000 0.06666667
  [5,] 0.00000000 0.06896552 0.00000000 0.00000000 0.13333333 0.00000000 0.00000000     0 0.00000000     0     0 0.00000000 0.00000000 0.00000000
  [6,] 0.00000000 0.03125000 0.00000000 0.12500000 0.05555556 0.05882353 0.25000000     0 0.00000000     0     0 0.00000000 0.11111111 0.00000000
  [7,] 0.06666667 0.24561404 0.00000000 0.04444444 0.21276596 0.19148936 0.04347826     0 0.00000000     0     0 0.02222222 0.09090909 0.02222222
  [8,] 0.12000000 0.27500000 0.00000000 0.03846154 0.23333333 0.16129032 0.07692308     0 0.00000000     0     0 0.04000000 0.07692308 0.00000000
  [9,] 0.08823529 0.25000000 0.00000000 0.09090909 0.17948718 0.21621622 0.08823529     0 0.00000000     0     0 0.02941176 0.12121212 0.02941176
 [10,] 0.22222222 0.13333333 0.00000000 0.25000000 0.17647059 0.11764706 0.10000000     0 0.00000000     0     0 0.00000000 0.22222222 0.00000000
            [,41]      [,42]      [,43]      [,44]      [,45]      [,46]      [,47]      [,48]      [,49]      [,50]      [,51]      [,52]      [,53]
  [1,] 0.00000000 0.20454545 0.05263158 0.05000000 0.12500000 0.05263158 0.06666667 0.20930233 0.07500000 0.43283582 0.12500000 0.14285714 0.04878049
  [2,] 0.00000000 0.00000000 0.25000000 0.00000000 0.00000000 0.00000000 0.00000000 0.13333333 0.14285714 0.03389831 0.00000000 0.00000000 0.00000000
  [3,] 0.00000000 0.20000000 0.25000000 0.40000000 0.25000000 0.25000000 0.18181818 0.13333333 0.00000000 0.03389831 0.25000000 0.18181818 0.14285714
  [4,] 0.00000000 0.16000000 0.00000000 0.12500000 0.10526316 0.06666667 0.26315789 0.21739130 0.26666667 0.20000000 0.16666667 0.20000000 0.18750000
  [5,] 0.00000000 0.05555556 0.00000000 0.00000000 0.10000000 0.20000000 0.07692308 0.12500000 0.12500000 0.05084746 0.22222222 0.07692308 0.00000000
  [6,] 0.00000000 0.10526316 0.14285714 0.11111111 0.18181818 0.14285714 0.06666667 0.11111111 0.00000000 0.06666667 0.08333333 0.23076923 0.00000000
  [7,] 0.02272727 0.22916667 0.02222222 0.09090909 0.08510638 0.04545455 0.17391304 0.16000000 0.08888889 0.43661972 0.10869565 0.12500000 0.11363636
  [8,] 0.04166667 0.18181818 0.00000000 0.03703704 0.10714286 0.04000000 0.17241379 0.22580645 0.16000000 0.30158730 0.14814815 0.21428571 0.07407407
  [9,] 0.03030303 0.20000000 0.02941176 0.08823529 0.17647059 0.06060606 0.22857143 0.27027027 0.08571429 0.35820896 0.17647059 0.19444444 0.11764706
 [10,] 0.00000000 0.10000000 0.00000000 0.22222222 0.07692308 0.00000000 0.13333333 0.10526316 0.00000000 0.10169492 0.07692308 0.21428571 0.20000000
            [,54]      [,55]      [,56]      [,57]      [,58]      [,59]      [,60]      [,61]      [,62]      [,63]      [,64]      [,65]      [,66]
  [1,] 0.05128205 0.11363636 0.32758621 0.04878049 0.16666667 0.11111111 0.04651163 0.09523810 0.07142857 0.05128205 0.35087719 0.09523810 0.12820513
  [2,] 0.20000000 0.07692308 0.02439024 0.00000000 0.07692308 0.00000000 0.00000000 0.00000000 0.11111111 1.00000000 0.07692308 0.00000000 0.50000000
  [3,] 0.20000000 0.16666667 0.05000000 0.14285714 0.16666667 0.15384615 0.25000000 0.22222222 0.00000000 0.00000000 0.05000000 0.22222222 0.12500000
  [4,] 0.13333333 0.25000000 0.26190476 0.00000000 0.25000000 0.18181818 0.10526316 0.15789474 0.16666667 0.06250000 0.26190476 0.15789474 0.17647059
  [5,] 0.00000000 0.07142857 0.07500000 0.00000000 0.15384615 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 0.10256410 0.09090909 0.11111111
  [6,] 0.00000000 0.06250000 0.09756098 0.37500000 0.13333333 0.28571429 0.44444444 0.27272727 0.00000000 0.00000000 0.09756098 0.27272727 0.09090909
  [7,] 0.04444444 0.22222222 0.45614035 0.04255319 0.10000000 0.16666667 0.08510638 0.13043478 0.08510638 0.02173913 0.40677966 0.10638298 0.08695652
  [8,] 0.03846154 0.20689655 0.40000000 0.11538462 0.20689655 0.20000000 0.10714286 0.14285714 0.10714286 0.03846154 0.43181818 0.18518519 0.11111111
  [9,] 0.05882353 0.22222222 0.46938776 0.11764706 0.22222222 0.21621622 0.14285714 0.17142857 0.02564103 0.02857143 0.44000000 0.17142857 0.11428571
 [10,] 0.11111111 0.05882353 0.12195122 0.20000000 0.12500000 0.11764706 0.16666667 0.07142857 0.00000000 0.00000000 0.12195122 0.15384615 0.00000000
            [,67]      [,68]      [,69]      [,70]      [,71]      [,72]      [,73] [,74]      [,75]      [,76]      [,77]      [,78]      [,79]
  [1,] 0.02564103 0.07317073 0.35416667 0.30434783 0.25000000 0.05000000 0.12195122     0 0.02631579 0.07692308 0.11904762 0.02631579 0.38181818
  [2,] 0.25000000 0.00000000 0.07142857 0.08695652 0.05263158 0.00000000 0.10000000     0 0.00000000 0.00000000 0.20000000 0.00000000 0.07894737
  [3,] 0.00000000 0.12500000 0.03448276 0.00000000 0.00000000 0.16666667 0.10000000     0 0.33333333 0.16666667 0.20000000 0.00000000 0.07894737
  [4,] 0.06666667 0.17647059 0.32258065 0.16129032 0.34782609 0.12500000 0.10000000     0 0.00000000 0.20000000 0.09523810 0.00000000 0.20930233
  [5,] 0.00000000 0.00000000 0.14814815 0.08333333 0.10526316 0.00000000 0.09090909     0 0.00000000 0.00000000 0.08333333 0.00000000 0.07692308
  [6,] 0.00000000 0.09090909 0.00000000 0.12000000 0.04545455 0.11111111 0.00000000     0 0.16666667 0.11111111 0.07142857 0.00000000 0.07317073
  [7,] 0.02222222 0.11111111 0.29090909 0.24528302 0.17307692 0.06666667 0.10638298     0 0.02272727 0.09090909 0.10416667 0.00000000 0.41379310
  [8,] 0.04000000 0.11111111 0.30769231 0.35294118 0.46428571 0.12000000 0.10344828     0 0.00000000 0.12000000 0.06451613 0.00000000 0.37777778
  [9,] 0.02941176 0.08333333 0.30434783 0.34146341 0.28205128 0.08823529 0.13888889     0 0.03030303 0.12121212 0.16666667 0.00000000 0.29090909
 [10,] 0.00000000 0.08333333 0.13333333 0.11538462 0.09090909 0.22222222 0.07142857     0 0.00000000 0.00000000 0.14285714 0.00000000 0.09756098
            [,80]      [,81]      [,82]      [,83]      [,84]      [,85]      [,86]      [,87]      [,88]      [,89]      [,90]      [,91]      [,92]
  [1,] 0.02439024 0.11627907 0.26086957 0.15909091 0.05263158 0.02564103 0.13953488 0.19565217 0.18604651 0.20370370 0.02631579 0.17073171 0.09302326
  [2,] 0.16666667 0.00000000 0.15000000 0.06666667 0.00000000 0.00000000 0.00000000 0.11111111 0.23076923 0.03448276 0.00000000 0.00000000 0.00000000
  [3,] 0.16666667 0.18181818 0.09523810 0.06666667 0.25000000 0.00000000 0.07692308 0.11111111 0.06666667 0.07142857 0.33333333 0.18181818 0.09090909
  [4,] 0.20000000 0.20000000 0.25925926 0.12500000 0.00000000 0.14285714 0.13636364 0.14814815 0.17391304 0.20588235 0.00000000 0.14285714 0.35294118
  [5,] 0.00000000 0.07692308 0.09090909 0.00000000 0.00000000 0.00000000 0.07142857 0.10526316 0.06250000 0.06896552 0.00000000 0.00000000 0.08333333
  [6,] 0.11111111 0.06666667 0.04000000 0.11764706 0.14285714 0.00000000 0.21428571 0.04545455 0.05555556 0.10000000 0.16666667 0.06666667 0.07142857
  [7,] 0.06666667 0.20000000 0.23076923 0.11764706 0.02222222 0.02222222 0.12244898 0.17307692 0.11764706 0.29090909 0.02272727 0.22727273 0.20454545
  [8,] 0.07692308 0.17241379 0.15789474 0.32142857 0.00000000 0.00000000 0.29629630 0.20588235 0.15625000 0.27500000 0.00000000 0.21428571 0.17857143
  [9,] 0.08823529 0.26470588 0.17777778 0.17948718 0.02941176 0.02941176 0.22222222 0.25000000 0.12195122 0.22448980 0.03030303 0.13157895 0.16666667
 [10,] 0.10000000 0.21428571 0.03846154 0.17647059 0.00000000 0.00000000 0.20000000 0.14285714 0.00000000 0.13333333 0.00000000 0.13333333 0.14285714
            [,93]      [,94]      [,95]      [,96]      [,97]      [,98]      [,99]     [,100]
  [1,] 0.09090909 0.10256410 0.30232558 0.26923077 0.18750000 0.40350877 0.23255814 0.43548387
  [2,] 0.00000000 0.33333333 0.10526316 0.06896552 0.10000000 0.02272727 0.05882353 0.01886792
  [3,] 0.08333333 0.00000000 0.05000000 0.06896552 0.04761905 0.07142857 0.05882353 0.03846154
  [4,] 0.20000000 0.05555556 0.10344828 0.27272727 0.26923077 0.24444444 0.20833333 0.20370370
  [5,] 0.07692308 0.00000000 0.10000000 0.10344828 0.09523810 0.06976744 0.05555556 0.07843137
  [6,] 0.14285714 0.00000000 0.09090909 0.09677419 0.08695652 0.09090909 0.05000000 0.09615385
  [7,] 0.20000000 0.06521739 0.19230769 0.35849057 0.14545455 0.45762712 0.15686275 0.53225806
  [8,] 0.09677419 0.07407407 0.23529412 0.30000000 0.34375000 0.37500000 0.30000000 0.33928571
  [9,] 0.13157895 0.02702703 0.18604651 0.27083333 0.30000000 0.38888889 0.20000000 0.44827586
 [10,] 0.06250000 0.00000000 0.08695652 0.12903226 0.13043478 0.11363636 0.15789474 0.11538462
 [ reached getOption("max.print") -- omitted 90 rows ]

Bei der Jaccard Similarity sind wiederum nur positive Werte ersichtlich. Eine Auswertung dieser geplotteten Werte ergibt, dass sehr wenige Werte über 0.3 liegen. Die Ähnlichkeit dieser ersten 10 Filme gegenüber den ersten 100 anderen Items ist also eher gering.

4.2 Vergleiche deine Implementierung der Cosine-basierten

Ähnlichkeitsmatrix für ordinale Ratings mit der via recommenderlab und einem anderen R-Paket erzeugten Ähnlichkeitsmatrix,

4.2.1 Vergleich Cosine Similiarty mit Recommenderlab

#recom_simcosin_4 <- as.matrix(similarity(normalize(MovieLense[1:number_user, 1:number_item]), which = "items", method = "cosine"))
recom_simcosin_4 <- as.matrix(similarity(MovieLense[1:number_user, 1:number_item], which = "items", method = "cosine"))

recom_simcosin_4[1:5,1:5]
                  Toy Story (1995) GoldenEye (1995) Four Rooms (1995) Get Shorty (1995) Copycat (1995)
Toy Story (1995)                NA        0.9821980         0.9308431         0.9664688      0.9730499
GoldenEye (1995)         0.9821980               NA         0.9455211         0.9598695      0.9629100
Four Rooms (1995)        0.9308431        0.9455211                NA         0.9687050      0.9472136
Get Shorty (1995)        0.9664688        0.9598695         0.9687050                NA      0.9368489
Copycat (1995)           0.9730499        0.9629100         0.9472136         0.9368489             NA
result_cossim_4_scaled <- 1 / 2 * (result_cossim_4 + 1)

result_cossim_4_scaled[1:5,1:5]
5 x 5 Matrix of class "dgeMatrix"
                  Toy Story (1995) GoldenEye (1995) Four Rooms (1995) Get Shorty (1995) Copycat (1995)
Toy Story (1995)         1.0000000        0.6893027         0.6778574         0.7042896      0.6770326
GoldenEye (1995)         0.6893027        1.0000000         0.5797779         0.7029339      0.6699096
Four Rooms (1995)        0.6778574        0.5797779         1.0000000         0.6994520      0.6142876
Get Shorty (1995)        0.7042896        0.7029339         0.6994520         1.0000000      0.6337300
Copycat (1995)           0.6770326        0.6699096         0.6142876         0.6337300      1.0000000

4.2.2 Vergleich Cosine Similiarity mit anderem R-Paket

library(lsa)

rec_simMat <- similarity(MovieLenseCompact_1[,1:5], which = "items")
rec_simMat
                                    101 Dalmatians (1996) 12 Angry Men (1957) 187 (1997) 2 Days in the Valley (1996)
12 Angry Men (1957)                             0.9491014                                                           
187 (1997)                                      0.9377585           0.9951661                                       
2 Days in the Valley (1996)                     0.9424520           0.9908561  0.9728694                            
20,000 Leagues Under the Sea (1954)             0.9636541           0.9846314  0.9824506                   0.9745629
# simMat_lsa <- cosine(DfforSimMatrix, y = NULL)

4.3 Vergleiche deine mittels Cosine Similarity erzeugten Ähnlichkeitsmatrix für ordinale Ratings mit der Jaccard-basierten Ähnlichkeitsmatrix für binäre Ratings.

5 Analyse Top-N Listen - IBCF vs UBCF

Aufgabe 5: Vergleiche und diskutiere Top-N Empfehlungen von IBCF und UBCF Modellen mit 30 Nachbarn und Cosine Similarity für den reduzierten Datensatz. ## 5.1 Berechne Top-15 Empfehlungen für Testkunden mit IBCF und UBCF ### 5.1.1 ribcf & rubcf Modell trainieren

ribcf_1 <- Recommender(training_1, "IBCF", param=list(k= 30, method = "cosine"))
ribcf_1
Recommender of type ‘IBCF’ for ‘realRatingMatrix’ 
learned using 320 users.
rubcf_1 <- Recommender(training_1, "UBCF", param=list(nn= 30, method = "cosine"))
rubcf_1
Recommender of type ‘UBCF’ for ‘realRatingMatrix’ 
learned using 320 users.
ribcf_2 <- Recommender(training_2, "IBCF", param=list(k= 30, method = "cosine"))
ribcf_2
Recommender of type ‘IBCF’ for ‘realRatingMatrix’ 
learned using 320 users.
rubcf_2 <- Recommender(training_2, "UBCF", param=list(nn= 30, method = "cosine"))
rubcf_2
Recommender of type ‘UBCF’ for ‘realRatingMatrix’ 
learned using 320 users.

Es wurden für beide reduzierten Datensätze jeweils ein ibcf und ubcf Recommender erstellt.

5.1.2 Model Predicitions erstellen

ribcftopNList_1 <- predict(ribcf_1, test_1, n=15)
ribcftopNList_1
Recommendations as ‘topNList’ with n = 15 for 80 users. 
rubcftopNList_1 <- predict(rubcf_1, test_1, n=15)
rubcftopNList_1
Recommendations as ‘topNList’ with n = 15 for 80 users. 
ribcftopNList_2 <- predict(ribcf_2, test_2, n=15)
ribcftopNList_2
Recommendations as ‘topNList’ with n = 15 for 80 users. 
rubcftopNList_2 <- predict(rubcf_2, test_2, n=15)
rubcftopNList_2
Recommendations as ‘topNList’ with n = 15 for 80 users. 

Nun wurden für beide Datensätze Predictions mit n = 15 und für 80 User berechnet.

5.1.3 Ausgabe von einer Prediction

# ausgabe von einem output
as(ribcftopNList_1, "list")[1:5]
$`0`
 [1] "Strictly Ballroom (1992)"                                   "Like Water For Chocolate (Como agua para chocolate) (1992)"
 [3] "Casablanca (1942)"                                          "In the Company of Men (1997)"                              
 [5] "Love Bug, The (1969)"                                       "My Left Foot (1989)"                                       
 [7] "African Queen, The (1951)"                                  "Fantasia (1940)"                                           
 [9] "Fear (1996)"                                                "Sphere (1998)"                                             
[11] "Dial M for Murder (1954)"                                   "Dead Man Walking (1995)"                                   
[13] "Citizen Kane (1941)"                                        "Smoke (1995)"                                              
[15] "What's Eating Gilbert Grape (1993)"                        

$`1`
 [1] "2 Days in the Valley (1996)"          "Adventures of Robin Hood, The (1938)" "Alice in Wonderland (1951)"          
 [4] "American in Paris, An (1951)"         "Being There (1979)"                   "Bringing Up Baby (1938)"             
 [7] "Cinema Paradiso (1988)"               "Crash (1996)"                         "Dead Man Walking (1995)"             
[10] "Ed Wood (1994)"                       "Grand Day Out, A (1992)"              "Hunt for Red October, The (1990)"    
[13] "Jackie Chan's First Strike (1996)"    "Jungle Book, The (1994)"              "Madness of King George, The (1994)"  

$`2`
 [1] "Time to Kill, A (1996)"            "City Hall (1996)"                  "City of Lost Children, The (1995)" "In the Company of Men (1997)"     
 [5] "Independence Day (ID4) (1996)"     "M*A*S*H (1970)"                    "Forrest Gump (1994)"               "Braveheart (1995)"                
 [9] "Dave (1993)"                       "Dead Poets Society (1989)"         "Mr. Holland's Opus (1995)"         "Cool Hand Luke (1967)"            
[13] "In the Line of Fire (1993)"        "Ghost (1990)"                      "Blade Runner (1982)"              

$`3`
 [1] "Bob Roberts (1992)"                           "Clerks (1994)"                                "Cool Hand Luke (1967)"                       
 [4] "Gandhi (1982)"                                "His Girl Friday (1940)"                       "Ice Storm, The (1997)"                       
 [7] "Pink Floyd - The Wall (1982)"                 "Postino, Il (1994)"                           "Rebel Without a Cause (1955)"                
[10] "Willy Wonka and the Chocolate Factory (1971)" "Shine (1996)"                                 "Seven (Se7en) (1995)"                        
[13] "Grosse Pointe Blank (1997)"                   "Three Colors: Red (1994)"                     "Boot, Das (1981)"                            

$`4`
 [1] "Monty Python's Life of Brian (1979)" "Henry V (1989)"                      "As Good As It Gets (1997)"          
 [4] "In the Company of Men (1997)"        "Junior (1994)"                       "Renaissance Man (1994)"             
 [7] "Cinema Paradiso (1988)"              "Dumbo (1941)"                        "White Squall (1996)"                
[10] "Boot, Das (1981)"                    "Strictly Ballroom (1992)"            "When Harry Met Sally... (1989)"     
[13] "Forbidden Planet (1956)"             "Amadeus (1984)"                      "American in Paris, An (1951)"       

Dies ist eine Übersicht der Empfehlungen für die ersten 5 User. Wie erfordert, wurden jeweils 15 Empfehlungen generiert. Auf den ersten Blick werden viele unterschiedlichen Filme empfohlen.

5.2 Vergleiche die Top-15 Empfehlungen und deren Verteilung und diskutiere Gemeinsamkeiten und Unterschiede zwischen IBCF und UBCF für alle Testkunden.

# df funktion erstellen
topN_df <- function(topNList){
  counts <- table(unlist(as.array(as(topNList, "list"))))
  df <- data.frame(Movie = names(counts), Count = unname(counts)) %>%
    select("Movie", "Count.Freq") %>%
    rename("Count" = "Count.Freq") %>%
    arrange(desc(Count))  
  df
}

# alle dfs erstellen
ribcftopN_df_1 <- topN_df(ribcftopNList_1)
ribcftopN_df_1
ribcftopN_df_2 <- topN_df(ribcftopNList_2)
ribcftopN_df_2

rubcftopN_df_1 <- topN_df(rubcftopNList_1)
rubcftopN_df_1
rubcftopN_df_2 <- topN_df(rubcftopNList_2)
rubcftopN_df_2
NA

Die ersten beiden Tabellen stellen die Empfehlungen und deren Anzahl basierend auf IBCF für die beiden Datensätze dar. In den Top 10 Empfehlungen sind sehr unterschiedliche Empfehlungen, es gibt kaum Überschneidungen. Für den ersten Datensatz wird ein Film maximal 11 mal, im zweiten maximal 15 mal empfohlen. Beim ersten Datensatz werden insgesamt 487 Filme und beim zweiten 407 empfohlen.

Die letzten beiden Tabellen stellen die Empfehlungen basierend auf UBCF für die beiden Datensätze dar. Die Top 10 Filme sind wieder sehr unterschiedlich. Grosse Unterschiede gibt es auch bei der Anzahl Vorkommen der Top Filme. Für den ersten Datensatz werden sie bis zu 30 mal empfohlen, während es beim zweiten maximal 14 mal war. Auch liegt die Anzahl Empfehlungen mit 301 vs 392 weit auseinander.

Für weitere Informationen visualisieren wir nun auch die Top Empfehlungen.

5.2.1 Verteilungen visualisieren

# funktion zur Visualisierung
top15_df_visualize <- function(topNList, subtitle){
  topNList %>% head(15) %>% 
    ggplot(aes(x = reorder(Movie, Count), y = Count)) +
    geom_bar(stat = "identity", fill = "limegreen", alpha = 0.5, color = "black") +
    coord_flip() +
    labs(x = "Movie", 
         y = "Anzahl", 
         title = "Top-15 Empfehlungen",
         subtitle = subtitle)
}

grid.arrange(top15_df_visualize(ribcftopN_df_1, "ribcf 1"),
             top15_df_visualize(rubcftopN_df_1, "rubcf 1"),
             ncol = 2)



grid.arrange(top15_df_visualize(ribcftopN_df_2, "ribcf 2"),
             top15_df_visualize(rubcftopN_df_2, "rubcf 2"),
             ncol = 2)

Dank der library gridExtra können wir die beiden Datensätze nebeneinander darstellen. Ersichtlich wird, wie schnell die Anzahl Empfehlungen pro Film abnimmt. In der ersten Lasche, IBCF, sieht man, dass die Anzahl linear abnimmt, nachdem die ersten fünf Filme gleich häufig empfohlen werden. Hingegen nehmen die Anzahl im zweiten Datensatz (Grafik rechts) zuerst schnell, bis etwa zum Niveau des ersten Datensatzes, dann linear ab. Bei UBCF, in der zweiten Lasche, nimmt die Anzahl bei beiden Datensätzen linear ab.

Die erwähnte Behauptung “Recommender Systeme machen für alle Nutzer die gleichen Empfehlungen” kann dank der Tabellen und Histogramme verworfen werden. Es werden viele unterschiedliche Filme empfohlen, vieleviele Filme werden nur wenigen Usern (<4) empfohlen.

6 Analyse Top-N Listen - Ratings

Aufgabe 6: Untersuche den Einfluss von Ratings (ordinale vs binäre Ratings) und Modelltyp (IBCF vs UBCF) auf Top-N Empfehlungen für den reduzierten Datensatz. Vergleiche den Anteil übereinstimmender Empfehlungen der Top-15 Liste für ## 6.1 IBCF vs UBCF, beide mit ordinalem Rating und Cosine Similarity für alle Testkunden,

compare_ibcf_ubcf <- function(ibcf, ubcf) {
  print(paste("Anzahl IBCF:", nrow(ibcf)))
  print(paste("Anzahl UBCF:", nrow(ubcf)))

  IntersectordRatCosine <- intersect(ibcf$Movie, ubcf$Movie)

  print(paste("Anzahl gemeinsame Empfehlungen:", length(IntersectordRatCosine)))
  print(paste("Anteil IBCF:", length(IntersectordRatCosine) / nrow(ibcf) * 100))
  print(paste("Anteil UBCF:", length(IntersectordRatCosine) / nrow(ubcf) * 100))
}

print("Erste Datenreduktion")
[1] "Erste Datenreduktion"
compare_ibcf_ubcf(ribcftopN_df_1, rubcftopN_df_1)
[1] "Anzahl IBCF: 487"
[1] "Anzahl UBCF: 301"
[1] "Anzahl gemeinsame Empfehlungen: 231"
[1] "Anteil IBCF: 47.4332648870637"
[1] "Anteil UBCF: 76.7441860465116"
print("Zweite Datenreduktion")
[1] "Zweite Datenreduktion"
compare_ibcf_ubcf(ribcftopN_df_2, rubcftopN_df_2)
[1] "Anzahl IBCF: 407"
[1] "Anzahl UBCF: 392"
[1] "Anzahl gemeinsame Empfehlungen: 226"
[1] "Anteil IBCF: 55.5282555282555"
[1] "Anteil UBCF: 57.6530612244898"

Erste Datenreduktion: Für IBCF werden 487 und UBCF 301 Filme empfohlen, dabei gibt es eine Übereinstimmung von 231 Filmen. Das entsprechen bei IBCF 47.5% und bei UBCF 76.7%. Zweite Datenreduktion: Für IBCF werden 407 und UBCF 392 Filme empfohlen, dabei gibt es eine Übereinstimmung von 226 Filmen. Das entsprechen bei IBCF 55% und bei UBCF 57%.

Insgesamt generieren also beide Methoden ähnliche Empfehlungen, rund die Hälfte bis 3/4 der Empfehlungen generiert auch die andere Methode. Auffällig ist hingegen beim ersten Datensatz, dass IBCF viel mehr Filme empfiehlt, während es beim zweiten etwa gleich viel sind.

Beim zweiten Datensatz ist auch der Anteil an Gemeinsamkeiten jeweils bei rund 55% und damit ausgeglichener als im ersten Datensatz. Ich kann mir vorstellen, dass das daran liegt, dass beim zweiten Datensatz die Sparsity der Matrix höher ist und damit mehr Spielraum offen ist.

6.2 IBCF vs UBCF, beide mit binärem Rating und Jaccard Similarity für alle Testkunden,

training_bin_1 <- binarize(training_1, minRating = 4)
test_bin_1 <- binarize(test_1, minRating = 4)

training_bin_2 <- binarize(training_2, minRating = 4)
test_bin_2 <- binarize(test_2, minRating = 4)

ribcf_bin_1 <- Recommender(training_bin_1, "IBCF", param=list(k= 30, method = "jaccard"))
ribcf_bin_1
Recommender of type ‘IBCF’ for ‘binaryRatingMatrix’ 
learned using 320 users.
rubcf_bin_1 <- Recommender(training_bin_1, "UBCF", param=list(nn= 30, method = "jaccard"))
rubcf_bin_1
Recommender of type ‘UBCF’ for ‘binaryRatingMatrix’ 
learned using 320 users.
ribcf_bin_2 <- Recommender(training_bin_2, "IBCF", param=list(k= 30, method = "jaccard"))
ribcf_bin_2
Recommender of type ‘IBCF’ for ‘binaryRatingMatrix’ 
learned using 320 users.
rubcf_bin_2 <- Recommender(training_bin_2, "UBCF", param=list(nn= 30, method = "jaccard"))
rubcf_bin_2
Recommender of type ‘UBCF’ for ‘binaryRatingMatrix’ 
learned using 320 users.
ribcftopNList_bin_1 = predict(ribcf_bin_1, test_bin_1, n=15)
ribcftopNList_bin_1
Recommendations as ‘topNList’ with n = 15 for 80 users. 
rubcftopNList_bin_1 = predict(rubcf_bin_1, test_bin_1, n=15)
rubcftopNList_bin_1
Recommendations as ‘topNList’ with n = 15 for 80 users. 
ribcftopNList_bin_2 = predict(ribcf_bin_2, test_bin_2, n=15)
ribcftopNList_bin_2
Recommendations as ‘topNList’ with n = 15 for 80 users. 
rubcftopNList_bin_2 = predict(rubcf_bin_2, test_bin_2, n=15)
rubcftopNList_bin_2
Recommendations as ‘topNList’ with n = 15 for 80 users. 
ribcftopN_df_bin_1 <- topN_df(ribcftopNList_bin_1)
ribcftopN_df_bin_1

ribcftopN_df_bin_2 <- topN_df(ribcftopNList_bin_2)
ribcftopN_df_bin_2

rubcftopN_df_bin_1 <- topN_df(rubcftopNList_bin_1)
rubcftopN_df_bin_1


rubcftopN_df_bin_2 <- topN_df(rubcftopNList_bin_2)
rubcftopN_df_bin_2
NA

Diese Auswertung entspricht der, der vorherigen Aufgabe, nur dass dieses mal mit binären Ratings und Jaccard Similarity gearbeitet wurde. Es wird auch hier ersichtlich, dass die Empfehlungen sehr unterschiedlich sind. Bei IBCF (erste zwei Tabellen) werden für den ersten Datensatz die Top Filme sehr viel häufiger (39 mal vs 16 mal) empfohlen. Das gleiche Muster, wenn aber schwächer, ist bei den UBCF ersichtlich.

print("Erste Datenreduktion binaer")
[1] "Erste Datenreduktion binaer"
compare_ibcf_ubcf(ribcftopN_df_bin_1, rubcftopN_df_bin_1)
[1] "Anzahl IBCF: 87"
[1] "Anzahl UBCF: 447"
[1] "Anzahl gemeinsame Empfehlungen: 6"
[1] "Anteil IBCF: 6.89655172413793"
[1] "Anteil UBCF: 1.34228187919463"
print("Zweite Datenreduktion binaer")
[1] "Zweite Datenreduktion binaer"
compare_ibcf_ubcf(ribcftopN_df_bin_2, rubcftopN_df_bin_2)
[1] "Anzahl IBCF: 411"
[1] "Anzahl UBCF: 519"
[1] "Anzahl gemeinsame Empfehlungen: 296"
[1] "Anteil IBCF: 72.0194647201946"
[1] "Anteil UBCF: 57.0327552986513"

Im Gegensatz zur vorherigen Aufgabe und den zweiten Datensatz, gibt es für den ersten fast keine gemeinsame Empfehlungen. Es fällt auch auf, dass für IBCF nur 87 Filme empfohlen werden. Diese Auswertung wurde mit minRating 4 für die binäre Klassifizierung berechnet. Mit Rating 3 sieht dieser Sachverhalt ähnlich aus, bei minRating 5 ist die Übereinstimmung aber wieder im normalen Bereich. Wieso minRating 3 und 4 so tiefe Übereinstimmungen generiert haben, können wir nicht nachvollziehe. Dass minRating 5 aber bessere Resultate generiert, liegt daran, dass nun nur noch wenige Items als 1 klassifiziert werden und damit weniger Filme zur Empfehlung zur Verfügung stellen.

6.3 UBCF mit ordinalem (Cosine Similarity) vs UBCF mit binärem Rating (Jaccard Similarity) für alle Testkunden.

compare_ubcf <- function(ibcf, ubcf) {
  print(paste("Anzahl UBCF ord:", nrow(ibcf)))
  print(paste("Anzahl UBCF bin:", nrow(ubcf)))

  IntersectordRatCosine <- intersect(ibcf$Movie, ubcf$Movie)

  print(paste("Anzahl gemeinsame Empfehlungen:", length(IntersectordRatCosine)))
  print(paste("Anteil UBCF ord:", length(IntersectordRatCosine) / nrow(ibcf) * 100))
  print(paste("Anteil UBCF bin:", length(IntersectordRatCosine) / nrow(ubcf) * 100))
}

Erstellung der Funktion und Berechnung des Resultats

print("Erste Datenreduktion")
[1] "Erste Datenreduktion"
compare_ubcf(rubcftopN_df_1, rubcftopN_df_bin_1)
[1] "Anzahl UBCF ord: 301"
[1] "Anzahl UBCF bin: 447"
[1] "Anzahl gemeinsame Empfehlungen: 207"
[1] "Anteil UBCF ord: 68.7707641196013"
[1] "Anteil UBCF bin: 46.3087248322148"
print("Zweite Datenreduktion")
[1] "Zweite Datenreduktion"
compare_ubcf(rubcftopN_df_2, rubcftopN_df_bin_2)
[1] "Anzahl UBCF ord: 392"
[1] "Anzahl UBCF bin: 519"
[1] "Anzahl gemeinsame Empfehlungen: 301"
[1] "Anteil UBCF ord: 76.7857142857143"
[1] "Anteil UBCF bin: 57.9961464354528"

Beim Vergleich von UBCF mit ordinalem und binärem Rating werden wieder mehr übereinstimmende Filme empfohlen. Für den ersten Datensatz werden 207 Filme bei beiden Modellen und beim zweiten Datensatz 301 übereinstimmende Filme empfohlen. Da bei beiden Datensätzen mit ordinalem Rating weniger Empfehlungen generiert werden, ist der Anteil Übereinstimmungen bei ordinalen Ratings entsprechend höher.

7 Analyse Top-N Listen - IBCF vs SVD

Aufgabe 7: Vergleiche Memory-based IBCF und Modell-based SVD Recommenders bezüglich Überschneidung ihrer Top-N Empfehlungen für die User-Item Matrix des reduzierten Datensatzes (Basis: reduzierter Datensatz, IBCF mit 30 Nachbarn und Cosine Similarity). Vergleiche wie sich der Anteil übereinstimmender Empfehlungen der Top-15 Liste für IBCF vs verschiedene SVD Modelle verändert, wenn die Anzahl der Singulärwerte für SVD von 10 auf 20, 30, 40, 50 verändert wird.

# Funktion fuer SVD Model
generate_SVD_topN_recomm <- function(train, test, svd_value = ksvd){
    recom_model <- Recommender(train, "SVD", param=list(k= svd_value))
    top_n_recom <- predict(recom_model, test, n=15)
  top_n_recom
}

# Funktion fuer verschiedene N
generate_SVD_topN_lists <- function(train, test, N_values) {
  rsvd_topN_lists <- list()
  for (i in 1:length(N_values)) {
    N <- N_values[i]
    list_name <- paste0("rsvd", N, "topNList")
    rsvd_topN_lists[[list_name]] <- generate_SVD_topN_recomm(train, test, N)
  }
  rsvd_topN_lists
}

Funktion zur Berechnung des Resultats

N_values <- c(10, 20, 30, 40, 50)
rsvd_topN_lists_1 <- generate_SVD_topN_lists(training_1, test_1, N_values)
print("Erster Datensatz")
[1] "Erster Datensatz"
rsvd_topN_lists_1
$rsvd10topNList
Recommendations as ‘topNList’ with n = 15 for 80 users. 

$rsvd20topNList
Recommendations as ‘topNList’ with n = 15 for 80 users. 

$rsvd30topNList
Recommendations as ‘topNList’ with n = 15 for 80 users. 

$rsvd40topNList
Recommendations as ‘topNList’ with n = 15 for 80 users. 

$rsvd50topNList
Recommendations as ‘topNList’ with n = 15 for 80 users. 
rsvd_topN_lists_2 <- generate_SVD_topN_lists(training_2, test_2, N_values)
print("Zweiter Datensatz")
[1] "Zweiter Datensatz"
rsvd_topN_lists_2
$rsvd10topNList
Recommendations as ‘topNList’ with n = 15 for 80 users. 

$rsvd20topNList
Recommendations as ‘topNList’ with n = 15 for 80 users. 

$rsvd30topNList
Recommendations as ‘topNList’ with n = 15 for 80 users. 

$rsvd40topNList
Recommendations as ‘topNList’ with n = 15 for 80 users. 

$rsvd50topNList
Recommendations as ‘topNList’ with n = 15 for 80 users. 
generate_topN_dfs <- function(rsvd_topN_lists) {
  topN_dfs <- list()
  
  for (i in 1:length(rsvd_topN_lists)) {
    list_name <- names(rsvd_topN_lists)[i]
    df_name <- paste0(list_name, "_df")
    topN_dfs[[df_name]] <- topN_df(rsvd_topN_lists[[i]])
  }
  
  topN_dfs
}

topN_df_svd_1 <- generate_topN_dfs(rsvd_topN_lists_1)
print("Erster Datensatz")
[1] "Erster Datensatz"
topN_df_svd_1
$rsvd10topNList_df

$rsvd20topNList_df

$rsvd30topNList_df

$rsvd40topNList_df

$rsvd50topNList_df
topN_df_svd_2 <- generate_topN_dfs(rsvd_topN_lists_2)
print("Zweiter Datensatz")
[1] "Zweiter Datensatz"
topN_df_svd_2
$rsvd10topNList_df

$rsvd20topNList_df

$rsvd30topNList_df

$rsvd40topNList_df

$rsvd50topNList_df
NA

Die ersten fünf Tabellen sind die Resultate für den ersten Datensatz. Es handelt sich aufsteigend um die Anzahl Singulärwerte von 10 bis 50. Die letzten fünf Tabellen beinhalten das gleiche Resultat, einfach für den zweiten Datensatz. Diese Auswertung wird noch nicht für die Beantwortung der Aufgabe verwendet, sondern gab uns einen ersten Überblick über die Resultate

compare_ibcf_svd <- function(ribcf, svd, svd_value) {
  intersect <- intersect(ribcf$Movie, svd$Movie)
  print(paste("Anzahl gemeinsame Empfehlungen SVD", svd_value, ":", length(intersect)))
  print(paste("Gemeinsamer relativer Anteil für Anzahl Singulärwerte", svd_value, ":", length(intersect) / nrow(ribcf) * 100))
}

print("Erster Datensatz")
[1] "Erster Datensatz"
compare_ibcf_svd(ribcftopN_df_1, topN_df_svd_1$rsvd10topNList_df, 10)
[1] "Anzahl gemeinsame Empfehlungen SVD 10 : 76"
[1] "Gemeinsamer relativer Anteil für Anzahl Singulärwerte 10 : 15.605749486653"
compare_ibcf_svd(ribcftopN_df_1, topN_df_svd_1$rsvd20topNList_df, 20)
[1] "Anzahl gemeinsame Empfehlungen SVD 20 : 86"
[1] "Gemeinsamer relativer Anteil für Anzahl Singulärwerte 20 : 17.6591375770021"
compare_ibcf_svd(ribcftopN_df_1, topN_df_svd_1$rsvd30topNList_df, 30)
[1] "Anzahl gemeinsame Empfehlungen SVD 30 : 93"
[1] "Gemeinsamer relativer Anteil für Anzahl Singulärwerte 30 : 19.0965092402464"
compare_ibcf_svd(ribcftopN_df_1, topN_df_svd_1$rsvd40topNList_df, 40)
[1] "Anzahl gemeinsame Empfehlungen SVD 40 : 105"
[1] "Gemeinsamer relativer Anteil für Anzahl Singulärwerte 40 : 21.5605749486653"
compare_ibcf_svd(ribcftopN_df_1, topN_df_svd_1$rsvd50topNList_df, 50)
[1] "Anzahl gemeinsame Empfehlungen SVD 50 : 117"
[1] "Gemeinsamer relativer Anteil für Anzahl Singulärwerte 50 : 24.0246406570842"
print("Zweiter Datensatz")
[1] "Zweiter Datensatz"
compare_ibcf_svd(ribcftopN_df_2, topN_df_svd_2$rsvd10topNList_df, 10)
[1] "Anzahl gemeinsame Empfehlungen SVD 10 : 10"
[1] "Gemeinsamer relativer Anteil für Anzahl Singulärwerte 10 : 2.45700245700246"
compare_ibcf_svd(ribcftopN_df_2, topN_df_svd_2$rsvd20topNList_df, 20)
[1] "Anzahl gemeinsame Empfehlungen SVD 20 : 20"
[1] "Gemeinsamer relativer Anteil für Anzahl Singulärwerte 20 : 4.91400491400491"
compare_ibcf_svd(ribcftopN_df_2, topN_df_svd_2$rsvd30topNList_df, 30)
[1] "Anzahl gemeinsame Empfehlungen SVD 30 : 24"
[1] "Gemeinsamer relativer Anteil für Anzahl Singulärwerte 30 : 5.8968058968059"
compare_ibcf_svd(ribcftopN_df_2, topN_df_svd_2$rsvd40topNList_df, 40)
[1] "Anzahl gemeinsame Empfehlungen SVD 40 : 27"
[1] "Gemeinsamer relativer Anteil für Anzahl Singulärwerte 40 : 6.63390663390663"
compare_ibcf_svd(ribcftopN_df_2, topN_df_svd_2$rsvd50topNList_df, 50)
[1] "Anzahl gemeinsame Empfehlungen SVD 50 : 27"
[1] "Gemeinsamer relativer Anteil für Anzahl Singulärwerte 50 : 6.63390663390663"

Für den ersten Datensatz werden bei SVD Wert 10 76 gemeinsame Empfehlungen mit IBCF generiert. Dies entspricht einem Anteil von 15.6% der Empfehlungen vom SVD Modell. Bis zur Anzahl von 50 Singulärwerten steigt die Anzahl gemeinsamer Empfehlungen auf 117, was einem Anteil von 24% entspricht.

8 Implementierung Top-N Metriken

Aufgabe 8 (DIY) ## 8.1 CoverageN

ribcf_8 <- Recommender(MovieLense, "IBCF", param=list(k= 30, method = "cosine"))
ribcf_8

ribcftopNList_8 <- predict(ribcf_8, MovieLense, n=15)
ribcftopNList_8

list_items_8 <- unique(unlist(as(ribcftopNList_8, "list"), use.names = FALSE))
len_items_8 <- length(list_items_8)

len_all_items_8 <- dim(MovieLense)[2]
len_all_items_8

coverageN <- len_items_8 / len_all_items_8
coverageN

41.7 % der vorhandenen Filme werden empfohlen.

8.2 NoveltyN

nratings(MovieLense) / len_all_items_8

9 Wahl des optimalen Recommenders

Aufgabe 9 ## 9.1 Verwende für die Evaluierung 10-fache Kreuzvalidierung

set.seed(1234)
scheme_1 <- evaluationScheme(MovieLenseCompact_1, method="cross-validation", k = 10, given=3, goodRating=5)
scheme_2 <- evaluationScheme(MovieLenseCompact_2, method="cross-validation", k = 10, given=3, goodRating=5)

print("Erste Datenreduktion")
scheme_1
print("Zweite Datenreduktion")
scheme_2

9.2 Begründe deine Wahl von Metriken und Modell

algorithms <- list("hybrid" = list(name = "HYBRID", param =list(recommenders = list(SVD = list(name="SVD", param=list(k = 40)),
                                                                                    POPULAR = list(name = "POPULAR", param = NULL)
                                                                                    ))),
                   "libmf" = list(name="LIBMF", param=list(dim=10)),
                   "popular items" = list(name="POPULAR", param=NULL),
                   "user-based CF" = list(name="UBCF", param=list(nn=50)),
                   "item-based CF" = list(name="IBCF", param=list(k=50)),
                   "SVD40" = list(name="SVD", param=list(k = 40)))

print("Erster Datensatz")
results_1 <- evaluate(scheme_1, algorithms, type = "topNList", n=c(10, 15, 20, 25, 30))
print("Zweiter Datensatz")
results_2 <- evaluate(scheme_2, algorithms, type = "topNList", n=c(10, 15, 20, 25, 30))
plot(results_1, annotate=c(1,3), legend="topleft")
plot(results_2, annotate=c(1,3), legend="topleft")

9.3 Analysiere das beste Modell für Top-N Recommendations mit N = 10, 15, 20, 25 und 30,

vieles blabaalabaaassss

9.4 Optimiere dein bestes Modell hinsichtlich Hyperparametern

algorithmsimprovedrecom <- list("popular items center" = list(name="POPULAR", param=NULL),
                   "popular items Z-score" = list(name="POPULAR", param=list(normalize="Z-score")))

resultsimprovedrecom_1 <- evaluate(scheme_1, algorithmsimprovedrecom, type = "topNList", n=c(10, 15, 20, 25, 30))
resultsimprovedrecom_2 <- evaluate(scheme_2, algorithmsimprovedrecom, type = "topNList", n=c(10, 15, 20, 25, 30))
plot(resultsimprovedrecom_1, annotate=c(1,3), legend="topleft")
plot(resultsimprovedrecom_2, annotate=c(1,3), legend="topleft")

Hinweis: Verwende für den Top-Movie Recommender die Filme mit den höchsten Durchschnittsratings. # 10 Implementierung Top-N Monitor Aufgabe 10 (DIY): Untersuche die relative Übereinstimmung zwischen Top-N Empfehlungen und präferierten Filmen für 4 unterschiedliche Modelle (z.B. IBCF und UBCF mit unterschiedlichen Ähnlichkeitsmetriken / Nachbarschaften sowie SVD mit unterschiedlicher Dimensionalitätsreduktion).

10.1 Fixiere 20 zufällig gewählte Testkunden für alle Modellvergleiche,

# select 20 random users
set.seed(1234)
testUsers <- sample(1:nrow(MovieLense), 20)
testUsers

# filter MovieLense by testUsers
MovieLenseTest <- MovieLense[testUsers,] 
MovieLenseTest

10.2 Bestimme den Anteil der Top-N Empfehlung nach Genres pro Kunde,

# get from every TestUsers the Top_N item list
ribcf_10 <- Recommender(MovieLenseTest, "IBCF", param=list(k= 30, method = "cosine"))

# predict Top-N items for every user
ribcftopNList_10 <- predict(ribcf_10, MovieLenseTest, n=15)

# create a list with the topN items for every user
ribcftopNList_10_list <- as(ribcftopNList_10, "list")

# create a tibble with the topN items for every user
ribcftopNList_10_tibble <- as_tibble(ribcftopNList_10_list)

# transform the tibble to a data frame
ribcftopNList_10_df <- as.data.frame(ribcftopNList_10_tibble)

# replace colname with testUsers
colnames(ribcftopNList_10_df) <- testUsers

# transpose data frame
ribcftopNList_10_df_transposed <- t(ribcftopNList_10_df)

# change ribcftopNList_10_df_transposed to a tibble
ribcftopNList_10_df_transposed_tibble <- as_tibble(ribcftopNList_10_df_transposed)

# add a column with the testUsers
ribcftopNList_10_df_transposed_tibble$testUsers <- testUsers

# pivot longer dataframe
ribcftopNList_10_df_transposed_tibble_pivot <- pivot_longer(ribcftopNList_10_df_transposed_tibble, cols = 1:15, names_to = "topN", values_to = "itemID")

# get genre from each item
ribcftopNList_10_df_transposed_tibble_pivot_genre <- left_join(ribcftopNList_10_df_transposed_tibble_pivot, MovieLenseMeta, by = c("itemID" = "title"))
ribcftopNList_10_df_transposed_tibble_pivot_genre

# drop columns topN, year, url
ribcftopNList_10_df_transposed_tibble_pivot_genre <- select(ribcftopNList_10_df_transposed_tibble_pivot_genre, -topN, -year, -url, -itemID)
ribcftopNList_10_df_transposed_tibble_pivot_genre
# pivot longer dataframe
ribcftopNList_10_df_transposed_tibble_pivot_genre %>% group_by(testUsers) %>%
  summarise(across(everything(), ~ sum(., is.na(.), 0)))

10.3 Bestimme pro Kunde den Anteil nach Genres seiner Top-Filme

(=Filme mit besten Bewertungen),

10.4 Vergleiche pro Kunde Top-Empfehlungen vs Top-Filme nach Genres,

10.5 Definiere eine Qualitätsmetrik für Top-N Listen und teste sie.

LS0tCnRpdGxlOiAiUlNZLU1DMSIKYXV0aG9yOiAiUGF0cmljayBTY2jDvHJtYW5uLCBTaSBCZW4gVHJhbiIKb3V0cHV0OiAKICBodG1sX25vdGVib29rOgogICAgdG9jOiBUcnVlCiAgICB0b2NfZmxvYXQ6IFRydWUKLS0tCiMgTWluaS1DaGFsbGVuZ2UgQmVzY2hyZWlidW5nCiMgRGF0ZW4gdW5kIExpYnJhcmllcwpgYGB7cn0KbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkocmVjb21tZW5kZXJsYWIpCmxpYnJhcnkoZ3JpZEV4dHJhKQpgYGAKCiMgRGF0ZW4gZWlubGVzZW4KYGBge3J9CmRhdGEoTW92aWVMZW5zZSkKYGBgCgpCZWltIEVpbmxlc2VuIGRlcyBEYXRlbnNhdHplcyB3ZXJkZW4gZHJlaSByZWFsUmF0aW5nTWF0cml4IGVpbmdlbGVzZW46IE1vdmllTGVuc2UsIE1vdmllTGVuc2VNZXRhIHVuZCBNb3ZpZUxlbnNlVXNlci4gV2lyIHVudGVyc3VjaGVuIG51biB6dWVyc3QgTW92aWVMZW5zZS4KCiMgTGlicmFyeSBNZXRob2RlbiB6dW0gRGF0ZW5zYXR6IE1vdmllTGVuc2UKYGBge3J9Cm1ldGhvZHMoY2xhc3MgPSBjbGFzcyhNb3ZpZUxlbnNlKSkKYGBgCkRpZXNlIMOcYmVyc2ljaHQgemVpZ3QgdW5zLCB3ZWxjaGUgTWV0aG9kZW4gbWl0IGRlciByZWFsUmF0aW5nTWF0cml4IGluIEtvbWJpbmF0aW9uIG1pdCBSZWNvbW1lbmRlcmxhYiBtw7ZnbGljaCBzaW5kLgoKIyBNb3ZpZUxlbnNlIERhdGFmcmFtZSBlcnN0ZWxsZW4KYGBge3J9Ck1vdmllTGVuc2VFREEgPC0gYXMoTW92aWVMZW5zZSwgImRhdGEuZnJhbWUiKQpgYGAKClVtIGRlbiBFREEtVGVpbCBsw7ZzZW4genUga8O2bm5lbiwgaGFiZW4gd2lyIGRpZSByZWFsUmF0aW5nTWF0cml4IGluIGVpbmVuIGRhdGEuZnJhbWUgdW1nZXdhbmRlbHQuCgojIEtvcGZ6ZWlsZSB1bmQgRnVzc3plaWxlIHZvbSBEYXRlbnNhdHogYXVzZ2ViZW4KYGBge3J9CmhlYWQoTW92aWVMZW5zZUVEQSkKCnRhaWwoTW92aWVMZW5zZUVEQSkKYGBgCgpVbSBlaW5lIElkZWUgZGVyIERhdGVuIHp1IGVyaGFsdGVuLCBoYWJlbiB3aXIgZGVuIEhlYWQgdW5kIFRhaWwgZGVzIERhdGFmcmFtZXMgYXVzZ2VnZWJlbi4gRXMgd2lyZCBlcnNpY2h0bGljaCwgZGFzcyBmw7xyIGplZGUgWmVpbGUgZWluIFVzZXIsIEl0ZW0gKEZpbG0pIHVuZCBkYXMgUmF0aW5nIGVyZmFzc3Qgc2luZC4KCiMgSW5mb3MgenVtIERhdGVuc2F0egpgYGB7cn0Kc3VtbWFyeShNb3ZpZUxlbnNlRURBKQpgYGAKCk1pdCBkZXIgU3VtbWFyeSBGdW5rdGlvbiBoYWJlbiB3aXIgdW5zIGVpbmVuIMOcYmVyYmxpY2sgw7xiZXIgZGllIFphaGxlbiBpbSBEYXRlbnNhdHogZXJzY2hhZmZlbi4gRXMgc2luZCBqZXdlaWxzIDk5JzM5MiBVc2VyIHVuZCBJdGVtcyBlcmZhc3N0LiBEaWUgUmF0aW5ncyByZWljaGVuIHZvbSBCZXJlaWNoIDEgYmlzIDUgdW5kIGRlciBNaXR0ZWx3ZXJ0IGJldHLDpGd0IDMuNTMgKE1lZGlhbiA0LjApCgojIDEgRXhwbG9yYXRpdmUgRGF0ZW5hbmFseXNlCkF1ZmdhYmUgMTogVW50ZXJzdWNoZSBkZW4gdm9sbHN0w6RuZGlnZW4gTW92aWVMZW5zZSBEYXRlbnNhdHogCihkLmguIHZvciBEYXRlbnJlZHVrdGlvbiEpIHVuZCBiZWFudHdvcnRlIGZvbGdlbmRlIEZyYWdlbjoKCiMjIDEuMSBXZWxjaGVzIHNpbmQgZGllIGFtIGjDpHVmaWdzdGVuIGdlc2NoYXV0ZW4gR2VucmVzL0ZpbG1lPwoKIyMjIDEuMS4xIFdlbGNoZXMgc2luZCBkaWUgYW0gaMOkdWZpZ3N0ZW4gZ2VzY2hhdXRlbiBGaWxtZT8KYGBge3J9Ck1vdmllTGVuc2VFREEgJT4lIAogIGdyb3VwX2J5KGl0ZW0pICU+JSAKICBzdW1tYXJpc2UoQW56YWhsID0gbigpKSAlPiUKICBhcnJhbmdlKGRlc2MoQW56YWhsKSkgJT4lIAogIGhlYWQobj0xMCkKYGBgCkRpZXNlIFRhYmVsbGUgemVpZ3QgdW5zIGRpZSBUb3AtMTAgZGVyIGFtIG1laXN0ZW4gZ2VzY2hhdXRlbiwgcmVzcC4gZ2VyYXRldGVuIEZpbG1lLiBFcyB3aXJkIGVyc2ljaHRsaWNoLCBkYXNzIFN0YXIgV2FycyAoMTk3NywgdmVybXV0bGljaCAiS3JpZWcgZGVyIFN0ZXJuZSIpIDU4MyBtYWwgZ2VzY2hhdXQgdW5kIGdlcmF0ZXQgd3VyZGUuIAoKIyMjIDEuMS4yIFdlbGNoZXMgc2luZCBkaWUgYW0gaMOkdWZpZ3N0ZW4gZ2VzY2hhdXRlbiBHZW5yZT8KYGBge3J9CiMgRnVsbCBKb2luIG1pdCBkZl9tb3ZpZXNfcmF0aW5nIHVuZCBNb3ZpZUxlbnNlTWV0YQpNb3ZpZUxlbnNlRURBX0pvaW5lZCA8LSBmdWxsX2pvaW4oTW92aWVMZW5zZUVEQSwgTW92aWVMZW5zZU1ldGEsIAogICAgICAgICAgYnkgPSBjKCJpdGVtIiA9ICJ0aXRsZSIpKSAlPiUgCiAgc2VsZWN0KC1jKCJ1c2VyIiwgIml0ZW0iLCAicmF0aW5nIiwgInllYXIiLCAidXJsIikpIAoKIyBBdWZzdW1taWVyZW4gZGVyIEdlbnJlIFNwYWx0ZW4KKGNvbFN1bXMoTW92aWVMZW5zZUVEQV9Kb2luZWQpKSAlPiUgc29ydChkZWNyZWFzaW5nID0gVFJVRSkKCmBgYApXaXIgZXJrZW5uZW4sIGRhc3MgZGFzIGFtIGjDpHVmaWdzdGVuIGdlc2NoYXV0ZW4gR2VucmUgIkRyYW1hIiBtaXQgMzknNDQ2IFJhdGluZ3MgaXN0LiBBdWYgZGVtIHp3ZWl0ZW4gUGxhdHogYmVmaW5kZXQgc2ljaCAiQ29tZGV5IiB1bmQgYXVmIGRlbSBkcml0dGVuICJBY3Rpb24iLiBBbSB3ZW5pZ3N0ZW4gaMOkdWZpZyB3dXJkZW4gIkRvY3VtZW50YXJ5IiB1bmQgInVua25vd24iIGdlc2NoYXV0LiAKCgojIyAxLjIgV2llIHZlcnRlaWxlbiBzaWNoIGRpZSBLdW5kZW5yYXRpbmdzIGdlc2FtdGhhZnQgdW5kIG5hY2ggR2VucmVzPwpgYGB7cn0KIyBEYXRhRnJhbWUgam9pbgpNb3ZpZUxlbnNlRURBX0pvaW5lZCA8LSBmdWxsX2pvaW4oTW92aWVMZW5zZUVEQSwgTW92aWVMZW5zZU1ldGEsIAogICAgICAgICAgYnkgPSBjKCJpdGVtIiA9ICJ0aXRsZSIpKQpgYGAKCkbDvHIgZGllc2UgRnJhZ2UgaGFiZW4gd2lyIGVpbmVuIG5ldWVuIERhdGVuc2F0eiAiTW92aWVMZW5zZUVEQV9Kb2luZWQiIGVyc3RlbGx0LiBFciBlcmdpYnQgc2ljaCBhdXMgTW92aWVMZW5zZUVEQSB1bmQgTW92aWVMZW5zZU1ldGEuIEZvbGdlbmQgbnVuIGRpZSBCZWFudHdvcnR1bmQgZGVyIEZyYWdlLgoKIyMjIDEuMi4xIFZlcnRlaWx1bmcgZGVyIEt1bmRlbnJhdGluZ3MgR2VzYW10aGFmdApgYGB7cn0KTW92aWVMZW5zZUVEQV9Kb2luZWQkcmF0aW5nIDwtIGFzLmZhY3RvcihNb3ZpZUxlbnNlRURBX0pvaW5lZCRyYXRpbmcpCgojIERhdGFmcmFtZSBVZWJlcnNpY2h0Ck1vdmllTGVuc2VFREFfSm9pbmVkICU+JSBncm91cF9ieShyYXRpbmcpICU+JQogIHN1bW1hcml6ZShBbnphaGwgPSBuKCkpCgojIFZpc3VlbGxlIERhcnN0ZWxsdW5nIG1pdHRlbHMgQmFycGxvdApNb3ZpZUxlbnNlRURBX0pvaW5lZCAlPiUgZ3JvdXBfYnkocmF0aW5nKSAlPiUKICBzdW1tYXJpemUoQW56YWhsID0gbigpKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gcmF0aW5nLCB5ID0gQW56YWhsKSkgKyAKICBnZW9tX2JhcihzdGF0ID0gImlkZW50aXR5IiwgCiAgICAgICAgICAgZmlsbCA9ICJsaWdodGJsdWUiLCAKICAgICAgICAgICBjb2xvciA9ICJibGFjayIpICsgCiAgbGFicyh4ID0gIlJhdGluZ3MiLCAKICAgICAgIHkgPSAiQW56YWhsIiwgCiAgICAgICB0aXRsZSA9ICJWZXJ0ZWlsdW5nIGRlciBLdW5kZW5yYXRpbmdzIEdlc2FtdGhhZnQiLAogICAgICAgc3VidGl0bGUgPSBwYXN0ZSgiR2VzYW10ZSBBbnphaGwgS3VuZGVucmF0aW5nczoiLCBkaW0oTW92aWVMZW5zZUVEQV9Kb2luZWQpWzFdKSkKYGBgCldpZSB3aXIgaW4gaW0gRGF0YWZyYW1lIHNvd2llIGltIEJhcnBsb3QgZXJrZW5uZW4sIHdlcmRlbiBhbSBow6R1Zmlnc3RlbiBkaWUgUmF0aW5ncyAzIHVuZCAgNCB2ZXJnZWJlbi4gUmF0aW5nIHZvbiAxIHVuZCAyIGtvbW1lbiBkZXV0bGljaCB3ZW5pZ2VyIHZvciwgYWxzIG3DtmdsaWNoZXIgR3J1bmQga8O2bm50ZSBzZWluLCBkYXNzIEZpbG1lIGRpZSBzY2hsZWNodCBzaW5kIGdhciBuaWNodCBiZXdlcnRldCB3dXJkZW4sIGRhIG1hbiBzaWNoIG5pY2h0IG1laHIgd2VpdGVyIG1pdCBzY2hsZWNodGVuIEZpbG1lbiBiZWZhc3NlbiBtw7ZjaHRlLiBBdXMgZWlnZW5lbiBFcmZhaHJ1bmdlbiBrw7ZubmVuIHdpciBzYWdlbiwgZGFzcyBtYW4gZWhlciBtZWhyIGJlcmVpdCBpc3QgZWluZW4gRmlsbSB6dSBiZXdlcnRlbiwgd2VubiBkaWVzZSBhdWNoIHdpcmtsaWNoIGd1dCBpc3QuIERhcyBSYXRpbmcgNSBrb21tdCBhbSBkcml0dGjDpHVmaWdzdGVuIHZvci4KCiMjIyAxLjIuMiBWZXJ0ZWlsdW5nIGRlciBLdW5kZW5yYXRpbmdzIG5hY2ggR2VucmUKYGBge3IsIGZpZy53aWR0aCA9IDEwLCBmaWcuaGVpZ2h0ID0gMTB9Ck1vdmllTGVuc2VFREFfSm9pbmVkJHJhdGluZyA8LSBhcy5pbnRlZ2VyKE1vdmllTGVuc2VFREFfSm9pbmVkJHJhdGluZykKCk1vdmllTGVuc2VFREFfSm9pbmVkICU+JSAKICBzZWxlY3QoLWMoIml0ZW0iLCAidXNlciIsICJ5ZWFyIiwgInVybCIpKSAlPiUgCiAgcGl2b3RfbG9uZ2VyKGNvbHM9YygidW5rbm93biIsICJBY3Rpb24iLCAiQWR2ZW50dXJlIiwgIkFuaW1hdGlvbiIsICJDaGlsZHJlbidzIiwKICAgICAgICAgICAgICAgICAgICAgICJDb21lZHkiLCAiQ3JpbWUiLCAiRG9jdW1lbnRhcnkiLCAiRHJhbWEiLCAiRmFudGFzeSIsCiAgICAgICAgICAgICAgICAgICAgICAiRmlsbS1Ob2lyIiwgIkhvcnJvciIsICJNdXNpY2FsIiwgIk15c3RlcnkiLCAiSG9ycm9yIiwKICAgICAgICAgICAgICAgICAgICAgICJNdXNpY2FsIiwgIk15c3RlcnkiLCAiUm9tYW5jZSIsICJTY2ktRmkiLCAiVGhyaWxsZXIiLAogICAgICAgICAgICAgICAgICAgICAgIldhciIsICJXZXN0ZXJuIiksCiAgICAgICAgICAgICAgIG5hbWVzX3RvID0gIkdlbnJlIiwgdmFsdWVzX3RvID0gImlzX2dlbnJlIikgJT4lCiAgZmlsdGVyKGlzX2dlbnJlID09IDEpICU+JSAKICBnZ3Bsb3QoYWVzKHggPSByYXRpbmcpKSArCiAgZ2VvbV9iYXIoZmlsbCA9ICJsaWdodGJsdWUiLCBjb2xvciA9ICJibGFjayIpICsKICBsYWJzKHggPSAiUmF0aW5ncyIsIAogICAgICAgeSA9ICJBbnphaGwiLCAKICAgICAgIHRpdGxlID0gIlZlcnRlaWx1bmcgZGVyIEt1bmRlbnJhdGluZ3MgbmFjaCBHZW5yZSIsCiAgICAgICBzdWJ0aXRsZSA9IHBhc3RlKCJHZXNhbXRlIEFuemFobCBLdW5kZW5yYXRpbmdzOiIsIGRpbShNb3ZpZUxlbnNlRURBX0pvaW5lZClbMV0pKSArIAogIGZhY2V0X3dyYXAofkdlbnJlKQpgYGAKSW4gZGVyIFZpc3VhbGlzaWVydW5nIGRlciBWZXJ0ZWlsdW5nIGRlciBLdW5kZW5yYXRpbmdzIHBybyBHZW5yZSBlcmtlbm5lbiB3aXIgYW5hbG9nLCB3aWUgYmVpIGRlciBWZXJ0ZWlsdW5nIGRlciBnZXNhbXRoYWZ0ZW4gS3VuZGVucmF0aW5ncywgZGFzcyBkaWUgUmF0aW5nIDMgdW5kIDQgYW0gbWVpc3RlbiB2ZXJnZWJlbiB3ZXJkZW4uIERpZXNlcyBNdXN0ZXIgaXN0IGJlaSBmYXN0IGFsbGVuIEdlbnJlcyBlcmtlbm5iYXIsIGVpbmZhY2ggbWl0IHVudGVyc2NoaWVkbGljaGVyIEludGVuc2l0w6R0IChBbnphaGwgUmF0aW5ncykuIAoKIyMgMS4zIFdpZSB2ZXJ0ZWlsZW4gc2ljaCBkaWUgbWl0dGxlcmVuIEt1bmRlbnJhdGluZ3MgcHJvIEZpbG0/CmBgYHtyfQojIERhdGFmcmFtZQpNb3ZpZUxlbnNlRURBICU+JSAKICBncm91cF9ieShpdGVtKSAlPiUgCiAgc3VtbWFyaXplKG1lYW5fcmF0aW5nX3Blcl9maWxtID0gbWVhbihyYXRpbmcpLAogICAgICAgICAgICBuX3JhdGluZ19wZXJfZmlsbSA9IG4oKSkgJT4lIAogIGFycmFuZ2Uobl9yYXRpbmdfcGVyX2ZpbG0pCgojIFZpc3VhbGlzaWVydW5nCk1vdmllTGVuc2VFREEgJT4lIAogIGdyb3VwX2J5KGl0ZW0pICU+JSAKICBzdW1tYXJpemUobWVhbl9yYXRpbmdfcGVyX2ZpbG0gPSBtZWFuKHJhdGluZykpICU+JSAKICBnZ3Bsb3QoYWVzKHggPSBtZWFuX3JhdGluZ19wZXJfZmlsbSkpICsgCiAgZ2VvbV9oaXN0b2dyYW0oY29sb3IgPSAiYmxhY2siLCBmaWxsID0gImxpZ2h0Ymx1ZSIsIGJpbndpZHRoID0gMC4xKSArCiAgICBsYWJzKHggPSAiUmF0aW5ncyIsIAogICAgICAgeSA9ICJBbnphaGwiLCAKICAgICAgIHRpdGxlID0gIlZlcnRlaWx1bmcgZGVyIE1pdHRsZXJlbiBLdW5kZW5yYXRpbmdzIHBybyBGaWxtIiwKICAgICAgIHN1YnRpdGxlID0gcGFzdGUoIkdlc2FtdGUgQW56YWhsIEt1bmRlbnJhdGluZ3M6IiwgZGltKE1vdmllTGVuc2VFREEpWzFdKSkKYGBgCldpciBlcmtlbm5lbiBpbSBQbG90IGRpZSBWZXJ0ZWlsdW5nIGR1cmNoc2Nobml0dGxpY2hlIFJhdGluZyBwcm8gRmlsbS4gQXVjaCBoaWVyIGlzdCBlcmtlbm5iYXIsIGRhc3MgZGllIG1laXN0ZW4gUmF0aW5ncyB6d2lzY2hlbiAzIHVuZCA0IGxpZWdlbi4gRWluZW4gQXVzcmVpc3NlciBnaWJ0IGVzIGJlaW0gUmF0aW5nIDEuIEJlaSBkZW4gbmF0w7xybGljaGVuL2dhbnp6w6RobGlnZW4gWmFobGVuIGVya2VubmVuIHdpciBlaW4gw7xiZXJyYXNjaGVuZGVzIE11c3RlcjogRGllIEFuemFobCBlcnNjaGVpbnQgamV3ZWlscyBow7ZoZXIgYWxzIGJlaSBkZW4gdW1saWVnZW5kZW4gUmF0aW5ncyBtaXQgS29tbWFzdGVsbGVuLiBEaWVzIGxpZWd0IGRhcmFuLCBkYXNzIGVzIEZpbG1lIGdpYnQgZGllIG51ciBlaW5lIG9kZXIgd2VuaWdlIEJld2VydHVuZ2VuIGJla29tbWVuIGhhYmVuIChzaWVoZSBhdXNnZWdlYmVuZXMgRGF0YWZhcm1lKS4KCiMjIDEuNCBXaWUgc3Rhcmsgc3RyZXVlbiBkaWUgUmF0aW5ncyB2b24gaW5kaXZpZHVlbGxlbiBLdW5kZW4/CmBgYHtyLCB3YXJuaW5nPUZBTFNFfQpNb3ZpZUxlbnNlRURBICU+JSBmaWx0ZXIodXNlciA9PSBjKDE6OSkpICU+JSAKICBnZ3Bsb3QoYWVzKHggPSB1c2VyLCB5ID0gcmF0aW5nKSkgKwogIGdlb21fdmlvbGluKGNvbG9yID0gImJsYWNrIiwgZmlsbCA9ICJsaWdodGJsdWUiKSArCiAgbGFicyh4ID0gIlVzZXIiLCAKICAgICAgIHkgPSAiUmF0aW5ncyIsIAogICAgICAgdGl0bGUgPSAiU3RyZXVldW5nIGRlciBSYXRpbmdzIHZvbiBpbmRpdmlkdWVsbGVuIEt1bmRlbiIsCiAgICAgICBzdWJ0aXRsZSA9ICJNb3ZpZUxlbnNlRGF0YSwgS3VuZGVuIDEtOSIpCmBgYApJbSBWaW9saW5lbnBsb3Qgc3RlbGxlbiB3aXIgZGllIGVyc3RlbiA5IFVzZXIgdW5kIGRlcmVuIFJhdGluZyBWZXJ0ZWlsdW5nZW4gZGFyLiBXaXIgZXJrZW5uZW4gaW0gUGxvdCwgZGFzcyBVc2VyIDIgdW5kIDggRmlsbWUgc2VociDDpGhubGljaGUgYmV3ZXJ0ZW4uIEJlaWRlIGJld2VydGVuIEZpbG1lIMO2ZnRlcnMgbWl0IGVpbmVyIDQgdW5kIGVoZXIgd2VuaWdlciBlaW5lIDMgdW5kIDUsIGFiZXIgbmllIDIgdW5kIDEuIFVzZXIgNSB1bmQgOSBiZXdlcnRlbiBGaWxtZSBoaW5nZWdlbiBpbSBnYW56ZW4gQmVyZWljaC4KCiMjIDEuNSBXZWxjaGVuIEVpbmZsdXNzIGhhdCBkaWUgTm9ybWllcnVuZyBkZXIgUmF0aW5ncyBwcm8gS3VuZGUgYXVmIGRlcmVuIFZlcnRlaWx1bmc/CmBgYHtyLCB3YXJuaW5nPUZBTFNFfQpNb3ZpZUxlbnNlbm9ybWFsaXplZCA8LSBub3JtYWxpemUoTW92aWVMZW5zZSkKTW92aWVMZW5zZUVEQV9Ob3JtYWxpemVkIDwtIChhcyhNb3ZpZUxlbnNlbm9ybWFsaXplZCwgImRhdGEuZnJhbWUiKSkKCk1vdmllTGVuc2VFREFfTm9ybWFsaXplZCAlPiUgZmlsdGVyKHVzZXIgPT0gYygxOjkpKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gdXNlciwgeSA9IHJhdGluZykpICsKICBnZW9tX3Zpb2xpbihjb2xvciA9ICJibGFjayIsIGZpbGwgPSAibGlnaHRibHVlIikgKwogIGxhYnMoeCA9ICJVc2VyIiwgCiAgICAgICB5ID0gIk5vcm1hbGlzaWVydGUgUmF0aW5ncyIsIAogICAgICAgdGl0bGUgPSAiTm9ybWFsaXNpZXJ0ZSBTdHJldWV1bmcgZGVyIFJhdGluZ3Mgdm9uIGluZGl2aWR1ZWxsZW4gS3VuZGVuIiwKICAgICAgIHN1YnRpdGxlID0gIk1vdmllTGVuc2VEYXRhLCBLdW5kZW4gMSAtIDkiKQpgYGAKRsO8ciBkaWUgTm9ybWllcnVuZyBkZXIgRGF0ZW4gaGFiZW4gd2lyIGRpZSBGdW5rdGlvbiB2b24gUmVjb21tZW5kZXJsYWIgdmVyd2VuZGV0LiBEZXIgTWl0dGVsd2VydCBkZXIgUmF0aW5ncyBwcm8gVXNlciBiZXRyw6RndCBudW4gTnVsbC4gSW0gUGxvdCB2ZXJzY2hpZWJ0IHNpY2ggbnVuIG5pY2h0IG51ciBkaWUgeS1BY2hzZSwgc29uZGVybiBhdWNoIGRpZSBCYW5kYnJlaXRlLiB1c2VyIDUgdW5kIDksIGRpZSBhdWYgZGVuIFJvaGRhdGVuIDEtNSBiZXdlcnRldCBoYWJlbiwgaGFiZW4gbnVuIHVudGVyc2NoaWVkbGljaGUgQmFuZGJyZWl0ZW4uIERpZXMgbGllZ3QgZGFyYW4sIGRhc3MgZGVyIE1pdHRlbHdlcnQgZGVyIGJlaWRlbiBVc2VyIHVudGVyc2NoaWVkbGljaCBpc3QuCgojIyAxLjYgV2VsY2hlIHN0cnVrdHVyZWxsZW4gQ2hhcmFrdGVyaXN0aWthICh6LkIuIFNwYXJzaXR5KSB1bmQgQXVmZsOkbGxpZ2tlaXRlbiB6ZWlndCBkaWUgVXNlci1JdGVtIE1hdHJpeD8KYGBge3J9CmltYWdlKHggPSBNb3ZpZUxlbnNlLCAKICAgICAgeGxhYiA9ICJJdGVtcyIsIAogICAgICB5bGFiID0gIlVzZXJzIiwgCiAgICAgIG1haW4gPSAiU3BhcmlzdHkgOTQzIHggMTY2NCBVc2VyLUl0ZW0gTWF0cml4IDk0MyB4IDE2NjQiKSAKCmltYWdlKE1vdmllTGVuc2VbMTo1MCwxOjUwXSwKICAgICAgeGxhYiA9ICJJdGVtcyIsCiAgICAgIHlsYWIgPSAiVXNlcnMiLCAKICAgICAgbWFpbiA9ICJTcGFyaXN0eSA1MCB4IDUwIFVzZXItSXRlbSBNYXRyaXgiKQoKIyBucmF0aW5ncyhNb3ZpZUxlbnNlKSB6YWVobHQgZGllIEFuemFobCB2b3JoYW5kZW5lbiBLb21iaW5hdGlvbmVuIHZvbiBVc2VyIHVuZCBJdGVtcwoobnJhdGluZ3MoTW92aWVMZW5zZSkgLyAoZGltKE1vdmllTGVuc2UpWzFdICogZGltKE1vdmllTGVuc2UpWzJdKSAqIDEwMCkKYGBgCkbDvHIgZGllIERhcnN0ZWxsdW5nIGRlciBTcGFyc2l0eSBoYWJlbiB3aXIgZGllIGltYWdlIEZ1bmt0aW9uIHZvbiBSZWNvbW1lbmRlcmxhYiB2ZXJ3ZW5kZXQuIEplZGUgWmVpbGUgdm9uIE1vdmllTGVuc2UgZW50c3ByaWNodCBlaW5lbSBCZW51dHplciB1bmQgamVkZSBTcGFsdGUgZWluZW0gRmlsbSB1bmQgZsO8ciBqZWRlIGdlc2NoYXV0ZSBLb21iaW5hdGlvbiB3aXJkIGVpbiBQaXhlbCBpbiBHcmF1c3R1ZmVuLCBqZSBuYWNoIFJhdGluZywgbWFya2llcnQuIEltIGVyc3RlbiBQbG90IHdpcmQgZXJzaWNodGxpY2gsIGRhc3MgZGllIGVyc3RlbiBVc2VyIHdlbmlnZXIgRmlsbWUgYmV3ZXJ0ZXQgaGFiZW4sIGRlbm4gb2JlbiByZWNodHMgc2luZCBrZWluZSBQdW5rdGUgbWVociBlcnNpY2h0bGljaC4gQXVjaCBpc3QgYXVmZsOkbGxpZywgZGFzcyBkaWUgZXJzdGVuIGV0d2EgNTAwIGjDpHVmaWdlciBnZXNjaGF1dCB3dXJkZW4sIGRlbm4gYmlzIHp1IGRpZXNlbSBCZXJlaWNoIHNpbmQgYW0gbWVpc3RlbiBQaXhlbCBlaW5nZWbDpHJidC4gVW0gZGllIERhcnN0ZWxsdW5nIGdlbmF1IHZlcnN0ZWhlbiB6dSBrw7ZubmVuLCBoYWJlbiB3aXIgaW0gendlaXRlbiBQbG90IG51ciBkaWUgZXJzdGVuIDUwIFVzZXIgdW5kIEl0ZW1zIGRhcmdlc3RlbGx0LiBEb3J0IGlzdCBkaWUgaG9oZSBTcGFyc2l0eSBndXQgZXJrZW5uYmFyLgpHZXNhbXRoYWZ0IGdpYnQgZXMgOTQzIHggMTY2NCA9IDHigJk1NjnigJkxNTIgS29tYmluYXRpb25lbiB6d2lzY2hlbiBVc2VyIHVuZCBGaWxtLiBBbGxlcmRpbmdzIGhhdCBuaWNodCBqZWRlciBOdXR6ZXIgamVkZW4gRmlsbSBnZXNlaGVuLCBhdXMgZGllc2VtIEdydW5kIGlzdCBlcyB3aWNodGlnIGRpZSBzcGFyc2l0eSBkZXIgTWF0cml4IHp1IGJldHJhY2h0ZW4uIEluIE1vdmllTGVuc2UgTWF0cml4IGZlaGxlbiBjYS4gOTQlIGRlciBLb21iaW5hdGlvbmVuLiBOdXIgZsO8ciA2LjMlIGRlciBtw7ZnbGljaGVuIEtvbWJpbmF0aW9uZW4gc2luZCBSYXRpbmdzIHZvcmhhbmRlbi4KCiMgMiBEYXRlbnJlZHVrdGlvbgpBdWZnYWJlIDI6IFJlZHV6aWVyZSBkZW4gTW92aWVMZW5zZSBEYXRlbnNhdHogYXVmIHJ1bmQgNDAwIEt1bmRlbiB1bmQgNzAwIEZpbG1lLCBpbmRlbSBkdSBGaWxtZSB1bmQgS3VuZGVuIG1pdCBzZWhyIHdlbmlnZW4gUmF0aW5ncyBlbnRmZXJuc3QuCgojIyAyLjEgVm9yYmVyZWl0dW5nCiMjIyAyLjEuMSBEYXRhRnJhbWUgbmV1IGVpbmxlc2VuCmBgYHtyfQpNb3ZpZUxlbnNlVG9DdXQgPC0gYXMoTW92aWVMZW5zZSwgImRhdGEuZnJhbWUiKQpNb3ZpZUxlbnNlVG9DdXQKYGBgCgojIyMgMi4xLjIgQXVzd2FobCBkZXIgNDAwIEt1bmRlbgpgYGB7cn0Kc2VsZWN0X3VzZXJfNDAwIDwtIGZ1bmN0aW9uKG1vdmllX2RmLCBzdGFydCwgZW5kKSB7CiAgc2VsZWN0ZWRfdXNlciA8LSBtb3ZpZV9kZiAlPiUgCiAgICBncm91cF9ieSh1c2VyKSAlPiUgCiAgICBzdW1tYXJpemUoQW56YWhsID0gbigpKSAlPiUgCiAgICBhcnJhbmdlKGRlc2MoQW56YWhsKSkgJT4lIAogICAgc2xpY2Uoc3RhcnQ6ZW5kKQogIHNlbGVjdGVkX3VzZXIKfQoKTW92aWVMZW5zZTQwMFVzZXJfMSA8LSBzZWxlY3RfdXNlcl80MDAoTW92aWVMZW5zZVRvQ3V0LCAwLCA0MDApCk1vdmllTGVuc2U0MDBVc2VyXzEKCk1vdmllTGVuc2U0MDBVc2VyXzIgPC0gc2VsZWN0X3VzZXJfNDAwKE1vdmllTGVuc2VUb0N1dCwgMjAwLCA1OTkpCk1vdmllTGVuc2U0MDBVc2VyXzIKYGBgCgpCZWkgZGVyIEF1c3dhaGwgZGVyIDQwMCBVc2VyIGhhYmVuIHdpciBkaXJla3QgYXVjaCB6d2VpIERhdGFmcmFtZXMgZXJzdGVsbHQsIGRhIHdpciBkaWUgTUMgenUgendlaXQgYmVhcmJlaXRlbi4gRsO8ciBQZXJzb24gMSBoYWJlbiB3aXIgZGllIDQwMCBVc2VyIG1pdCBkZW4gbWVpc3RlbiBSYXRpbmdzIGF1c2dld8OkaGx0IHVuZCBmw7xyIFBlcnNvbiAyIFVzZXIgMjAwIGJpcyA2MDAuIFdpciBoYWJlbiBkaWVzZXMgVm9yZ2VoZW4gZ2V3w6RobHQgdW0gc2ljaGVyenVzdGVsbGVuLCBkYXNzIG51ciBlaW5lIFRlaWwgZGVyIFVzZXIgaW4gYmVpZGVuIERhdGFmcmFtZXMgZW50aGFsdGVuIGlzdC4gQWx0ZXJuYXRpdiBow6R0dGVuIHdpciB2b24gZGVuIFRvcCA1MDAgVXNlciB6dWbDpGxsaWcgODAlIGbDvHIgUGVyc29uIDEgdW5kIDIgdmVyd2VuZGV0LCBkYW5uIGjDpHR0ZSBkaWUgw5xiZXJsYXBwdW5nIGFiZXIgc2VociBob2NoIHNlaW4ga8O2bm5lbiwgc28gaXN0IGVzIG51ciBkaWUgSMOkbGZ0LgoKIyMjIDIuMS4zIEF1c3dhaGwgZGVyIDcwMCBNb3ZpZXMKYGBge3J9CnNlbGVjdF9pdGVtXzcwMCA8LSBmdW5jdGlvbihtb3ZpZV9kZiwgc3RhcnQsIGVuZCkgewogIHNlbGVjdGVkX2l0ZW0gPC0gTW92aWVMZW5zZVRvQ3V0ICU+JSAKICBncm91cF9ieShpdGVtKSAlPiUgCiAgc3VtbWFyaXNlKEFuemFobCA9IG4oKSkgJT4lIAogIGFycmFuZ2UoZGVzYyhBbnphaGwpKSAlPiUgCiAgc2xpY2Uoc3RhcnQ6ZW5kKQp9CgpNb3ZpZUxlbnNlNzAwSXRlbXNfMSA8LSBzZWxlY3RfaXRlbV83MDAoTW92aWVMZW5zZVRvQ3V0LCAwLCA3MDApCk1vdmllTGVuc2U3MDBJdGVtc18xCgpNb3ZpZUxlbnNlNzAwSXRlbXNfMiA8LSBzZWxlY3RfaXRlbV83MDAoTW92aWVMZW5zZVRvQ3V0LCAxNTAsIDg0OSkKTW92aWVMZW5zZTcwMEl0ZW1zXzIKCmBgYAoKRGFzIGdsZWljaGUgVm9yZ2VoZW4gaGFiZW4gd2lyIGJlaSBkZW4gRmlsbWVuIGdld8OkaGx0LiAKCiMjIyAyLjEuNCBEYXRhRnJhbWUgc2NobmVpZGVuCmBgYHtyfQpkZl9jdXR0ZXIgPC0gZnVuY3Rpb24obW92aWVfZGYsIHNlbGVjdGVkX3VzZXIsIHNlbGVjdGVkX2l0ZW1zKSB7CiAgbW92aWVfZGZfY3V0IDwtIG1vdmllX2RmICU+JQogICAgICBmaWx0ZXIodXNlciAlaW4lIGMoc2VsZWN0ZWRfdXNlciR1c2VyKSkKICBtb3ZpZV9kZl9jdXQgPC0gbW92aWVfZGZfY3V0ICU+JSAKICAgICAgZmlsdGVyKGl0ZW0gJWluJSBjKHNlbGVjdGVkX2l0ZW1zJGl0ZW0pKQogIG1vdmllX2RmX2N1dAp9CgpNb3ZpZUxlbnNlQ3V0XzEgPC0gZGZfY3V0dGVyKE1vdmllTGVuc2VUb0N1dCwgTW92aWVMZW5zZTQwMFVzZXJfMSwgTW92aWVMZW5zZTcwMEl0ZW1zXzEpCk1vdmllTGVuc2VDdXRfMQoKTW92aWVMZW5zZUN1dF8yIDwtIGRmX2N1dHRlcihNb3ZpZUxlbnNlVG9DdXQsIE1vdmllTGVuc2U0MDBVc2VyXzIsIE1vdmllTGVuc2U3MDBJdGVtc18yKQpNb3ZpZUxlbnNlQ3V0XzIKYGBgCgpVbnRlcnN1Y2hlIHVuZCBkb2t1bWVudGllcmUgZGllIEVpZ2Vuc2NoYWZ0ZW4gZGVzIHJlZHV6aWVydGVuIERhdGVuc2F0emVzIHVuZCBiZXNjaHJlaWJlIGRlbiBFZmZla3QgZGVyIERhdGVucmVkdWt0aW9uLCBkLmguCgojIyAyLjIgQW56YWhsIEZpbG1lIHVuZCBLdW5kZW4gc293aWUgU3BhcnNpdHkgdm9yIHVuZCBuYWNoIERhdGVucmVkdWt0aW9uLAojIyMgMi4yLjEgVm9yIGRlciBEYXRlbnJlZHVrdGlvbgpgYGB7cn0KaW1hZ2UoTW92aWVMZW5zZSwgCiAgICAgIHhsYWIgPSAiSXRlbXMiLCAKICAgICAgeWxhYiA9ICJVc2VycyIsIAogICAgICBtYWluID0gIlZvciBEYXRlbnJlZHVrdGlvbiwgVXNlci1JdGVtIE1hdHJpeCA5NDMgeCAxNjY0IikgCgpzcGFyc2l0eV90ZXh0IDwtIGZ1bmN0aW9uKHJlYWxyYXRpbmdfbWF0cml4KSB7CiAgcHJpbnQocGFzdGUoIkFuemFobCB2b3JoYW5kZW5lIFVzZXItSXRlbSBSYXRpbmcgaW4iLCBucmF0aW5ncyhyZWFscmF0aW5nX21hdHJpeCkgLyAoZGltKHJlYWxyYXRpbmdfbWF0cml4KVsxXSAqIGRpbShyZWFscmF0aW5nX21hdHJpeClbMl0pICogMTAwLCAiJSIpKQogIHByaW50KHBhc3RlKCJTcGFyc2l0eSBkZXIgTWF0cml4IiwgMTAwIC0gKG5yYXRpbmdzKHJlYWxyYXRpbmdfbWF0cml4KSAvIChkaW0ocmVhbHJhdGluZ19tYXRyaXgpWzFdICogZGltKHJlYWxyYXRpbmdfbWF0cml4KVsyXSkgKiAxMDApLCAiJSIpKQp9CgpzcGFyc2l0eV90ZXh0KE1vdmllTGVuc2UpCgpgYGAKWnVyIFJlcGV0aXRpb24gc3RlbGxlbiB3aXIgbm9jaG1hbHMgZGllIFNwYXJzaXR5IGFscyBCaWxkIGRhciB1bmQgYmVyZWNobmVuIGRlbiBXZXJ0LgoKCiMjIyAyLjIuMiBOYWNoIGRlciAxLiBEYXRlbnJlZHVrdGlvbgpgYGB7cn0KTW92aWVMZW5zZUNvbXBhY3RfMSA8LSBhcyhNb3ZpZUxlbnNlQ3V0XzEsICJyZWFsUmF0aW5nTWF0cml4IikKaW1hZ2UoTW92aWVMZW5zZUNvbXBhY3RfMSwKICAgICAgeGxhYiA9ICJJdGVtcyIsIAogICAgICB5bGFiID0gIlVzZXJzIiwgCiAgICAgIG1haW4gPSAiTmFjaCBEYXRlbnJlZHVrdGlvbiAxLCBVc2VyLUl0ZW0gTWF0cml4IDQwMCB4IDcwMCIpCgpzcGFyc2l0eV90ZXh0KE1vdmllTGVuc2VDb21wYWN0XzEpCmBgYAoKRsO8ciBkZW4gZXJzdGVuIERhdGVuc2F0eiB3aXJkIGVyc2ljaHRsaWNoLCBkYXNzIGRpZSBSYXRpbmdzIGdlZ2Vuw7xiZXIgZGVtIHVyc3Byw7xuZ2xpY2hlbiBEYXRlbnNhdHogZ2xlaWNobcOkc3NpZyB2ZXJ0ZWlsdCBzaW5kLiBWZXJlaW56ZWx0IHNpbmQgZsO8ciBVc2VyICh6LkIuIGltIEJlcmVpY2ggOTAtMTUwKSB1bmQgSXRlbXMgKHouQiBCZXJlaWNodCB1bSA2MDApIGR1bmtsZXJlIEJlcmVpY2hlIGVya2VubmJhci4gSW4gZGllc2VuIGTDvHJmdGVuIGRpZSBSYXRpbmdzIGjDtmhlciB1bmQgU3BhcnNpdHkgZ2VyaW5nZXIgc2Vpbi4KRGllIFNwYXJzaXR5IGJldHLDpGd0IG51biBhdWNoIG51ciBub2NoIGV0d2EgNzUlIHVuZCBmw7xyIDI1JSBkZXIgbcO2Z2xpY2hlbiBLb21iaW5hdGlvbmVuIHp3aXNjaGVuIFVzZXIgdW5kIEl0ZW0gd3VyZGVuIFJhdGluZ3MgYW5nZWdlYmVuLgoKRGllc2Ugc3RhcmtlIMOEbmRlcnVuZyB3YXIgYWJlciB6dSBlcndhcnRlbiwgZGEgd2lyIGRpZSBVc2VyIHVuZCBJdGVtcyBtaXQgZGVuIG1laXN0ZW4gUmF0aW5ncyBhdXNnZXfDpGhsdCBoYWJlbi4KCiMjIyAyLjIuMyBOYWNoIGRlciAyLiBEYXRlbnJlZHVrdGlvbgpgYGB7cn0KTW92aWVMZW5zZUNvbXBhY3RfMiA8LSBhcyhNb3ZpZUxlbnNlQ3V0XzIsICJyZWFsUmF0aW5nTWF0cml4IikKaW1hZ2UoTW92aWVMZW5zZUNvbXBhY3RfMiwKICAgICAgeGxhYiA9ICJJdGVtcyIsIAogICAgICB5bGFiID0gIlVzZXJzIiwgCiAgICAgIG1haW4gPSAiTmFjaCBEYXRlbnJlZHVrdGlvbiAyLCBVc2VyLUl0ZW0gTWF0cml4IDQwMCB4IDcwMCIpCgpzcGFyc2l0eV90ZXh0KE1vdmllTGVuc2VDb21wYWN0XzIpCgpgYGAKRsO8ciBkZW4gendlaXRlbiBEYXRlbnNhdHogd2lyZCBlcnNpY2h0bGljaCwgZGFzcyBkaWUgUmF0aW5ncyBnZWdlbsO8YmVyIGRlbSB1cnNwcsO8bmdsaWNoZW4gRGF0ZW5zYXR6IGdsZWljaG3DpHNzaWcgdmVydGVpbHQgc2luZCwgZ2VnZW7DvGJlciBkZW0gZXJzdGVuIERhdGVuc2F0eiBhYmVyIHNpY2h0YmFyIHdlbmlnZXIgUmF0aW5ncyB2b3JoYW5kZW4gc2luZC4gRHVua2xlcmUgQmVyZWljaCwgd2llIGJlaSBEYXRlbnNhdHoxIHNpbmQga2F1bSBtZWhyIHp1IGVya2VubmVuLgpEaWUgU3BhcnNpdHkgYmV0csOkZ3QgbGllZ3QgbnVuIGJlaSA5My42JSwgc2llIGlzdCBnZWdlbsO8YmVyIGRlbSBlcnN0ZW4gRGF0ZW5zYXR6IGFsc28gZGV1dGxpY2ggYW5nZXN0aWVnZW4sIGxpZWd0IGFiZXIgYmVyZWl0cyBpbSBCZXJlaWNoIGRlcyB1cnNwcsO8bmdsaWNoZW4gV2VydGVzLgpEaWVzZXIgQW5zdGllZyB3YXIgenUgZXJ3YXJ0ZW4sIGRhIHdpciBuaWNodCBtZWhyIGRpZSBVc2VyIHVuZCBJdGVtcyBtaXQgZGVuIG1laXN0ZW4gUmF0aW5ncyBhdXNnZXfDpGhsdCBoYWJlbiwgc29uZGVybiB6LkIuIGJlaSBkZW4gVXNlcm4gYmVpIFRvcCAyMDAgYW5nZWZhbmdlbiBoYWJlbi4KCiMjIDIuMyBNaXR0bGVyZSBLdW5kZW5yYXRpbmdzIHBybyBGaWxtIHZvciB1bmQgbmFjaCBEYXRlbnJlZHVrdGlvbiwKYGBge3J9Cm1lYW5fcmF0aW5nX3Blcl9maWxtX3ZpeiA8LSBmdW5jdGlvbihtb3ZpZV9kZikgewogIG1vdmllX2RmICU+JSAKICBncm91cF9ieShpdGVtKSAlPiUgCiAgc3VtbWFyaXplKG1lYW5fcmF0aW5nX3Blcl9maWxtID0gbWVhbihyYXRpbmcpKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gbWVhbl9yYXRpbmdfcGVyX2ZpbG0pKSArIAogIGdlb21faGlzdG9ncmFtKGNvbG9yID0gImJsYWNrIiwgZmlsbCA9ICJsaWdodGJsdWUiLCBiaW53aWR0aCA9IDAuMSkgKwogICAgbGFicyh4ID0gIlJhdGluZ3MiLCAKICAgICAgIHkgPSAiQW56YWhsIiwgCiAgICAgICB0aXRsZSA9ICJNaXR0bGVyZSBLdW5kZW5yYXRpbmdzIFZlcnRlaWx1bmciLAogICAgICAgc3VidGl0bGUgPSBwYXN0ZSgiR2VzYW10ZSBBbnphaGwgS3VuZGVucmF0aW5nczoiLCBkaW0obW92aWVfZGYpWzFdKSkgKwogICAgZ2VvbV92bGluZSh4aW50ZXJjZXB0ID0gbWVhbihtb3ZpZV9kZiRyYXRpbmcpLCBjb2xvciA9ICJyZWQiLCBsaW5ldHlwZSA9ICJkYXNoZWQiLCBzaXplID0gMC41KQp9CiMgVm9yIHJlZHVrdGlvbgpwcmludChtZWFuX3JhdGluZ19wZXJfZmlsbV92aXooTW92aWVMZW5zZUVEQSkpCiMgbmFjaCAxLiBSZWR1dGtpb24KcHJpbnQobWVhbl9yYXRpbmdfcGVyX2ZpbG1fdml6KE1vdmllTGVuc2VDdXRfMSkpCiMgbmFjaCAyLiBSZWR1a3Rpb24KcHJpbnQobWVhbl9yYXRpbmdfcGVyX2ZpbG1fdml6KE1vdmllTGVuc2VDdXRfMikpCmBgYApEaWUgZXJzdGUgVmlzdWFsaXNpZXJ1bmcgemVpZ3QgZGVuIGJlcmVpdHMgYmVrYW5udGVuIFBsb3QgbWl0IGRlbiBtaXR0bGVyZW4gS3VuZGVucmF0aW5ncyBmw7xyIGRlbiBnZXNhbXRlbiBEYXRlbnNhdHouIFBsb3QgMiB1bmQgMyB6ZWlndCBkaWUgc2VsYmUgQXVzd2VydHVuZyBmw7xyIGRpZSBiZWlkZW4gZ2Vrw7xyenRlbiBEYXRlbnPDpHR6ZS4KSW4gZGVuIFZpc3VhbGlzaWVydW5nZW4gZXJrZW5uZW4gd2lyLCBkYXNzIGRlciBNaXR0ZWx3ZXJ0IGRlciBLdW5kZW5yYXRpbmcgZsO8ciBkZW4gdXJzcHLDvG5nbGljaGVuLCBzb3dpZSBhdWNoIGbDvHIgZGllIGJlaWRlbiByZWR1emllcnRlbiBEYXRlbnPDpHR6ZSwgbmljaHQgZ3Jvc3NhcnRpZyDDpG5kZXJ0LiBEaWUgTWl0dGVsd2VydGUgYmVmaW5kZW4gc2ljaCBiZWkgYWxsZW4gaW0gQmVyZWljaCB2b24gMy41LiBXYXMgYWJlciBlcmtlbm5iYXIgd2lyZCwgaXN0LCBkYXNzIGJlaSBkZXIgMS4gUmVkdWt0aW9uIGRpZSBob2hlIEFuemFobCBSYXRpbmcgYmVpIGRlbiBuYXTDvHJsaWNoZW4vZ2FuenphaGxpZ2VuIFphaGxlbiB3ZWdnZWZhbGxlbiBpc3QuIFdlaXRlcmhpbiBzaW5kIGJlaSBhbGxlbiBWaXN1YWxpc2llcnVuZ2VuIGVya2VubmJhciwgZGFzcyBkaWUgbWVpc3RlbiBSYXRpbmcgaW0gQmVyZWljaCB2b24gMyBiaXMgNCBsaWVnZW4uIAoKIyMgMi40IEbDvHIgR3J1cHBlbjogUXVhbnRpZml6aWVyZSDigJxJbnRlcnNlY3Rpb24gb3ZlciBVbmlvbuKAnSBkZXIgUmF0aW5ncyBkZXIgdW50ZXJzY2hpZWRsaWNoIHJlZHV6aWVydGVuIERhdGVuc8OkdHplLgpgYGB7cn0KaW50ZXJzZWN0X2pvaW4gPC0gaW5uZXJfam9pbihNb3ZpZUxlbnNlQ3V0XzEsIE1vdmllTGVuc2VDdXRfMiwgYnkgPSBjKCJ1c2VyIiwgIml0ZW0iKSkKaW50ZXJzZWN0X2pvaW4KCnVuaW9uX2pvaW4gPC0gZnVsbF9qb2luKE1vdmllTGVuc2VDdXRfMSwgTW92aWVMZW5zZUN1dF8yLCBieSA9IGMoInVzZXIiLCAiaXRlbSIpKQp1bmlvbl9qb2luCgpwYXN0ZSgiRWluZSBJbnRlcnNlY3Rpb24gb3ZlciBVbmlvbiB2b24iLCBkaW0oaW50ZXJzZWN0X2pvaW4pWzFdIC8gZGltKHVuaW9uX2pvaW4pWzFdICogMTAwLCAiJSwgendpc2NoZW4gZGVuIGJlaWRlbiByZWR1emllcnRlbiBEYXRlbnPDpHR6ZW4iKQoKYGBgCgpadXIgQmVhbnR3b3J0dW5nIGRpZXNlciBGcmFnZSBoYWJlbiB3aXIgZWluZXJzZWl0cyBlaW5lbiBEYXRlbnNhdHogbWl0IERhdGVuLCBkaWUgaW4gYmVpZGVuIERhdGVuc8OkdHplbiB2b3JoYW5kZW4gc2luZCBlcnN0ZWxsdCB1bmQgZGllc2VuIG1pdCBkZXIgZ2VzYW10ZW4gQW56YWhsIERhdGVuIHZlcmdsaWNoZW4uIEVzIHplaWd0IHNpY2gsIGRhc3MgZXMgZWluZSDDnGJlcnNjaG5laWR1bmcgdm9uIDE1LjYlIHp3aXNjaGVuIGRlbiBiZWlkZW4gcmVkdXppZXJ0ZW4gRGF0ZW5zw6R0emVuIGdpYnQuIERpZXNlciBlaGVyIHRpZWZlIFdlcnQgw7xiZXJyYXNjaHQsIHdlaWwgei5CLiA1MCUgZGVyIFVzZXIgw7xiZXJlaW5zdGltbWVuLiBBYmVyIGF1ZmdydW5kIGRlciBob2hlbiBTcGFyc2l0eSBpc3QgZGllIMOcYmVyc2NobmVpZHVuZyBkZXIgRGF0ZW4gdmllbCB0aWVmZXIuCgojIDMgQW5hbHlzZSDDhGhubGljaGtlaXRzbWF0cml4CkF1ZmdhYmUgMzogRXJ6ZXVnZSBlaW5lbiBJQkNGIFJlY29tbWVuZGVyIHVuZCBhbmFseXNpZXJlIGRpZSDDhGhubGljaGtlaXRzbWF0cml4IGRlcyB0cmFpbmllcnRlbiBNb2RlbGxlcyBmw7xyIGRlbiByZWR1emllcnRlbiBEYXRlbnNhdHouCgojIyAzLjEgWmVybGVnZSBkZW4gcmVkdXppZXJ0ZW4gTW92aWVMZW5zZSBEYXRlbnNhdHogaW4gZWluIGRpc2p1bmt0ZXMgVHJhaW5pbmdzLXVuZCBUZXN0ZGF0ZW5zZXQgaW0gVmVyaMOkbHRuaXMgNDoxLApgYGB7cn0KdHJhaW5fdGVzdF9zcGxpdCA8LSBmdW5jdGlvbihtb3ZpZV9kZiwgc3BsaXQgPSAwLjgpIHsKICBuIDwtIGRpbShtb3ZpZV9kZilbMV0KICBuX3RyYWluIDwtIHJvdW5kKG4gKiBzcGxpdCkKICBuX3Rlc3QgPC0gbiAtIG5fdHJhaW4KICB0cmFpbmluZyA8LSBtb3ZpZV9kZlsxOm5fdHJhaW5dCiAgdGVzdCA8LSBtb3ZpZV9kZlsobl90cmFpbiArIDEpOm5dCiAgcmV0dXJuKGxpc3QodHJhaW5pbmcsIHRlc3QpKQp9Cgp0cmFpbl90ZXN0X2xpc3RfMSA8LSB0cmFpbl90ZXN0X3NwbGl0KE1vdmllTGVuc2VDb21wYWN0XzEpCnRyYWluaW5nXzEgPC0gdHJhaW5fdGVzdF9saXN0XzFbWzFdXQp0ZXN0XzEgPC0gdHJhaW5fdGVzdF9saXN0XzFbWzJdXQp0cmFpbmluZ18xCnRlc3RfMQoKdHJhaW5fdGVzdF9saXN0XzIgPC0gdHJhaW5fdGVzdF9zcGxpdChNb3ZpZUxlbnNlQ29tcGFjdF8yKQp0cmFpbmluZ18yIDwtIHRyYWluX3Rlc3RfbGlzdF8yW1sxXV0KdGVzdF8yIDwtIHRyYWluX3Rlc3RfbGlzdF8yW1syXV0KdHJhaW5pbmdfMgp0ZXN0XzIKCmBgYApCZWlkZSByZWR1emllcnRlbiBEYXRlbnPDpHR6ZSB3dXJkZW4gaW0gVmVyaMOkbHRuaXMgNDoxLCAoNCBUZWlsZSBUcmFpbmluZyB1bmQgMSBUZWlsIFRlc3QpIHJlZHV6aWVydC4KCiMjIDMuMiBUcmFpbmllcmUgZWluIElCQ0YgTW9kZWxsIG1pdCAzMCBOYWNoYmFybiB1bmQgQ29zaW5lIFNpbWlsYXJpdHkKYGBge3J9CnJpYmNmXzEgPC0gUmVjb21tZW5kZXIodHJhaW5pbmdfMSwgIklCQ0YiLCBwYXJhbT1saXN0KGs9IDMwLCBtZXRob2QgPSAiY29zaW5lIikpCnJpYmNmXzEKCnJpYmNmXzIgPC0gUmVjb21tZW5kZXIodHJhaW5pbmdfMiwgIklCQ0YiLCBwYXJhbT1saXN0KGs9IDMwLCBtZXRob2QgPSAiY29zaW5lIikpCnJpYmNmXzIKYGBgCkVzIHd1cmRlbiBqZXdlaWxzIGbDvHIgYmVpZGUgcmVkdXppZXJ0ZW4gRGF0ZW5zYWV0emUgZWluIElCQ0YgTW9kZWxsIG1pdCAzMCBOYWNoYmFybiB1bmQgZGVyIENvc2luZSBTaW1pbGFyaXR5IG1pdHRlbHMgZGVyIHZvbiBSZWNvbW1lbmRlcmxhYiB6dXIgVmVyZsO8Z3VuZyBnZXN0ZWxsdGVuIE1ldGhvZGUgdHJhaW5pZXJ0LiBEaWUgQXVzd2VydHVuZyBiZXN0w6R0aWd0LCBkYXNzIGRhcyBUcmFpbmluZyBtaXR0ZWxzIDMyMCBVc2VybiwgcmVzcC4gODAlIGRlciB1cnNwcsO8bmdsaWNoZW4gNDAwLCBkdXJjaGdlZsO8aHJ0IHd1cmRlLgoKIyMgMy4zIEJlc3RpbW1lIGRpZSBWZXJ0ZWlsdW5nIGRlciBGaWxtZSwgd2VsY2hlIGJlaSBJQkNGIGbDvHIgcGFhcndlaXNlIMOEaG5saWNoa2VpdHN2ZXJnbGVpY2hlIHZlcndlbmRldCB3ZXJkZW4KYGBge3J9CnJpYmNmX3NpbV9pdGVtX2RmIDwtIGZ1bmN0aW9uKHJpYmNmKSB7CiAgIyBtb2RlbAogIHJpYmNmX21vZGVsIDwtIGdldE1vZGVsKHJpYmNmKQogICMgZGF0YWZyYW1lIGVyc3RlbGxlbgogIHJpYmNmX3NpbV9kZiA8LSBhcy5kYXRhLmZyYW1lKGNvbFN1bXMocmliY2ZfbW9kZWwkc2ltID4gMCkpCiAgIyBJdGVtIGFscyBuZXVlIFNwYWx0ZSBoaW56dWZ1ZWdlbiB1bmQgSW5kZXggZW50ZmVybmVuCiAgcmliY2Zfc2ltX2RmXyA8LSBjYmluZChpdGVtID0gcm93bmFtZXMocmliY2Zfc2ltX2RmKSwgcmliY2Zfc2ltX2RmKQogIHJvd25hbWVzKHJpYmNmX3NpbV9kZl8pIDwtIE5VTEwKICAjIHJldHVybiBkZgogIHJpYmNmX3NpbV9kZl8KfQoKcmliY2Zfc2ltX3ZpeiA8LSBmdW5jdGlvbihyaWJjZl9zaW1fZGZfLCBuX3JlZHVjKSB7CiAgICByaWJjZl9zaW1fZGZfICU+JQogICAgcmVuYW1lKEFuemFobCA9IDIpICU+JSAKICAgIGdncGxvdChhZXMoeCA9IEFuemFobCkpICsgCiAgICBnZW9tX2hpc3RvZ3JhbShiaW53aWR0aCA9ICAwLjEpICsKICAgIGxhYnModGl0bGUgPSAiVmVydGVpbHVuZyBkZXIgw4RobmxpY2hrZWl0c3ZlcmdsZWljaGUiLAogICAgICAgICB4ID0gIkFuemFobCBGaWxtZSBhbHMgTmFjaGJhciIsIAogICAgICAgICB5ID0gIkFuemFobCIsCiAgICAgICAgIHN1YnRpdGxlID0gcGFzdGUoInJpYmNmIiwgbl9yZWR1YykpCn0KCnJpYmNmX3NpbV9kZl8xIDwtIHJpYmNmX3NpbV9pdGVtX2RmKHJpYmNmXzEpCnJpYmNmX3NpbV92aXoocmliY2Zfc2ltX2RmXzEsIDEpCgpyaWJjZl9zaW1fZGZfMiA8LSByaWJjZl9zaW1faXRlbV9kZihyaWJjZl8yKQpyaWJjZl9zaW1fdml6KHJpYmNmX3NpbV9kZl8yLCAyKQoKCmBgYApJbSBIaXN0b2dyYW1tIGVya2VubnQgbWFuIGRpZSBBbnphaGwgRmlsbWUgZGllIGFscyBOYWNoYmFyIGJlaSBlaW5lbSBhbmRlcmVuIEZpbG0gYXVmdGF1Y2hlbi4gQmVpZGUgUGxvdHMgc2luZCBkZXV0bGljaCB1bnRlcnNjaGllZGxpY2gKCiMjIDMuNCBCZXN0aW1tZSBkaWUgRmlsbWUsIGRpZSBhbSBow6R1Zmlnc3RlbiBpbiBkZXIgQ29zaW5lLcOEaG5saWNoa2VpdHNtYXRyaXggYXVmdGF1Y2hlbiB1bmQgYW5hbHlzaWVyZSBkZXJlbiBWb3Jrb21tZW4gdW5kIFJhdGluZ3MgaW0gcmVkdXppZXJ0ZW4gRGF0ZW5zYXR6LgoKYGBge3IsIHdhcm5pbmc9RkFMU0V9CnRvcF8xMF9pdGVtX3NpbSA8LSBmdW5jdGlvbihyaWJjZl9zaW1fZGZfLCBuX3JlZHVjKSB7CiAgcmVzdWx0IDwtIHJpYmNmX3NpbV9kZl8gJT4lIAogIHJlbmFtZShBbnphaGwgPSAyKSAlPiUgCiAgYXJyYW5nZShkZXNjKEFuemFobCkpICU+JSAKICB0b3BfbigxMCkKICAgIAogIHByaW50KHJlc3VsdCkKICAgIAogIHJlc3VsdCAlPiUgICAKICBnZ3Bsb3QoYWVzKHggPSBBbnphaGwsIHkgPSBpdGVtKSkgKwogICMgYXJyYW5nZSBkZXNjCiAgZ2VvbV9jb2woYWxwaGEgPSAwLjUsIGNvbG9yID0gImJsYWNrIiwgZmlsbCA9ICJsaW1lZ3JlZW4iKSArCiAgbGFicyh0aXRsZSA9ICJUb3AgMTAgRmlsbWUgZGllIGFtIGjDpHVmaWdzdGVuIGluIGRlciBOYWNoYmFyc2NoYWZ0IGFuZGVyZSBGaWxtZSBhdWZ0YXVjaGVuIiwKICAgICAgIHggPSAiQW56YWhsIEZpbG0gYWxzIE5hY2hiYXIiLCAKICAgICAgIHkgPSAiRmlsbWUiLAogICAgICAgc3VidGl0bGUgPSBwYXN0ZSgicmliY2YiLCBuX3JlZHVjKSkKfQogIAp0b3BfMTBfaXRlbV9zaW0ocmliY2Zfc2ltX2RmXzEsIDEpCnRvcF8xMF9pdGVtX3NpbShyaWJjZl9zaW1fZGZfMiwgMikKCmBgYAoKRsO8ciBqZWRlbiBkZXIgYmVpZGVuIERhdGVuc8OkdHplIGhhYmVuIHdpciBlaW5lbiBEYXRhZnJhbWUgdW5kIFBsb3QgbWl0IGRlbiBGaWxtZW4sIGRpZSBhbSBow6R1Zmlnc3RlbiBpbiBkZXIgQ29zaW5lLcOEaG5saWNoa2VpdHNtYXRyaXggYXVmdGF1Y2hlbiwgZXJzdGVsbHQuIEJlaSBkZW4gdG9wIDEwIEZpbG1lbiBzaW5kIGtlaW5lIEdlbWVpbnNhbWtlaXRlbiBlcnNpY2h0bGljaC4gRGllIEFuemFobCBkZXIgVm9ya29tbWVuIGlzdCBhYmVyIMOkaG5saWNoLCBkZXIgaMO2Y2hzdGUgV2VydCBpc3Qgendpc2NoZW4gMTUwIHVuZCAxNjAgdW5kIGRpZSBOdW1tZXIgMTAgbGllZ3QgYmVpIDEyMCBWb3Jrb21tZW4uCgojIDQgSW1wbGVtZW50aWVydW5nIMOEaG5saWNoa2VpdHNtYXRyaXgKQXVmZ2FiZSA0IChESVkpOiBJbXBsZW1lbnRpZXJlIGVpbmUgRnVua3Rpb24genVyIGVmZml6aWVudGVuCkJlcmVjaG51bmcgdm9uIHNwYXJzZW4gw4RobmxpY2hrZWl0c21hdHJpemVuIGbDvHIgSUJDRiBSUyB1bmQKYW5hbHlzaWVyZSBkaWUgUmVzdWx0YXRlIGbDvHIgMTAwIHp1ZsOkbGxpZyBnZXfDpGhsdGUgRmlsbWUuCgojIyA0LjEgSW1wbGVtZW50aWVyZSBlaW5lIEZ1bmt0aW9uLCB1bSAoYSkgZsO8ciBvcmRpbmFsZSBSYXRpbmdzIGVmZml6aWVudApkaWUgQ29zaW5lIFNpbWlsYXJpdHkgdW5kIChiKSBmw7xyIGJpbsOkcmUgUmF0aW5ncyBlZmZpemllbnQgZGllIEphY2NhcmQKU2ltaWxhcml0eSB6dSBiZXJlY2huZW4sCmBgYHtyfQpudW1iZXJfdXNlciA8LSAxMDAKbnVtYmVyX2l0ZW0gPC0gMTAwCmBgYAoKRGllc2UgVmFyaWFibGVuIGhhYmVuIHdpciBmw7xyIGRpZSBFbnR3aWNrbHVuZyBkZXIgRnVua3Rpb25lbiB2ZXJ3ZW5kZXQuIFdpciBrb25udGUgZGFtaXQgZWluZmFjaCBrbGVpbmVyZSwgei5CLiA1LCBEYXRlbnPDpHR6ZSBzbGljZW4uCgojIyMgNC4xLjEgQ29zaW5lIFNpbWlsYXJpdHkgCmBgYHtyfQpnZXRfY29zc2ltXzQgPC0gZnVuY3Rpb24oUmF0aW5nTWF0cml4LCBuX3VzZXIsIG5faXRlbSl7CiAKICBzbGljZWRfbWF0cml4IDwtIGdldFJhdGluZ01hdHJpeChSYXRpbmdNYXRyaXhbMTpuX3VzZXIsIDE6bl9pdGVtXSkKICAKICBzbGljZWRfbWF0cml4X3QgPC0gdChzbGljZWRfbWF0cml4KQogIAogIHRlbXBfc2ltIDwtIHNsaWNlZF9tYXRyaXhfdCAvIHNxcnQocm93U3VtcyhzbGljZWRfbWF0cml4X3QgKiogMikpCgogIGNvc3NpbV9tYXRyaXggPC0gdGVtcF9zaW0gJSolIHQodGVtcF9zaW0pCgogIGNvc3NpbV9tYXRyaXgKfQpgYGAKCmBgYHtyfQpyZXN1bHRfY29zc2ltXzQgPC0gZ2V0X2Nvc3NpbV80KE1vdmllTGVuc2UsIG51bWJlcl91c2VyLCBudW1iZXJfaXRlbSkKcmVzdWx0X2Nvc3NpbV80WzE6MjAsMToyMF0KYGBgCgpNaXQgZGVyIGVyc3RlbGx0ZW4gRnVua3Rpb24gaGFiZW4gd2lyIGbDvHIgZGVuIGdlc2FtdGVuIE1vdmllTGVuc2UgRGF0ZW5zYXR6IGRpZSBDb3NpbmUgU2ltaWxhcml0eSBNYXRyaXggYmVyZWNobmV0LiBVbSBkYXMgUmVzdWx0YXQgbGVzYmFyIGRhcnp1c3RlbGxlbiwgemVpZ2VuIHdpciBoaWVyIG51ciBkaWUgZXJzdGVuIGbDvG5mIEl0ZW0uIEJlaSBkZXIgQW5hbHlzZSBkZXIgZXJzdGVuIDIwIEl0ZW1zIHd1cmRlIGVyc2ljaHRsaWNoLCBkYXNzIGRpZSBXZXJ0ZSB6d2lzY2hlbiAwIHVuZCAxIGxpZWdlbi4gTmVnYXRpdmUgU2ltaWxhcml0aWVzIHNpbmQgbmljaHQgZXJzaWNodGxpY2guIFdpZSBtaXQgZGlyIGJlc3Byb2NoZW4gdW5kIGhlcmdlbGVpdGV0LCBpc3QgZGFzIGFiZXIgdmVyc3TDpG5kbGljaCwgZGEgYXVmZ3J1bmQgZGVyIG5pY2h0LW5lZ2F0aXZlbiBSYXRpbmdzIGRlciBtYXhpbWFsZSBXaW5rZWwgOTDCsCBiZXRyw6RndC4gSMOkdHRlbiB3aXIgbWl0IG5vcm1pZXJ0ZW4gUmF0aW5ncyBnZWFyYmVpdGV0LCB3w6RyZW4gYXVjaCBuZWdhdGl2ZSBXZXJ0ZSBhdWZnZXRyZXRlbi4KCiMjIyA0LjEuMiBKYWNjYXJkIFNpbWlsYXJpdHkKYGBge3J9CmdldF9qYWNjYXJkc2ltXzQgPC0gZnVuY3Rpb24oUmF0aW5nTWF0cml4LCBuX3VzZXIsIG5faXRlbSl7CiAgCiAgc2xpY2VkX21hdHJpeF9iaW4gPC0gYXMoYmluYXJpemUoUmF0aW5nTWF0cml4WzE6bl91c2VyLCAxOm5faXRlbV0sIG1pblJhdGluZz00KSwgIm1hdHJpeCIpCiAgCiAgc2xpY2VkX21hdHJpeF9iaW5fdCA8LSB0KHNsaWNlZF9tYXRyaXhfYmluKQogIAogIG1hdHJpeF9jb3Jzc3Byb2QgPC0gdGNyb3NzcHJvZChzbGljZWRfbWF0cml4X2Jpbl90KQogIAogIGltIDwtIHdoaWNoKG1hdHJpeF9jb3Jzc3Byb2QgPiAwLCBhcnIuaW5kPVRSVUUpCiAgYiA8LSByb3dTdW1zKHNsaWNlZF9tYXRyaXhfYmluX3QpCiAgQWltIDwtIG1hdHJpeF9jb3Jzc3Byb2RbaW1dCiAgCiAgSiA9IHNwYXJzZU1hdHJpeCgKICAgICAgICAgICAgaSA9IGltWywxXSwKICAgICAgICAgICAgaiA9IGltWywyXSwKICAgICAgICAgICAgeCA9IEFpbSAvIChiW2ltWywxXV0gKyBiW2ltWywyXV0gLSBBaW0pLAogICAgICAgICAgICBkaW1zID0gZGltKG1hdHJpeF9jb3Jzc3Byb2QpCiAgICAgICkKICAKICBKIDwtIGRhdGEubWF0cml4KEopCiAgCiAgSgp9CgpgYGAKCmBgYHtyfQpnZXRfamFjY2FyZHNpbV80KE1vdmllTGVuc2UsIG51bWJlcl91c2VyLCBudW1iZXJfaXRlbSkKYGBgCgpCZWkgZGVyIEphY2NhcmQgU2ltaWxhcml0eSBzaW5kIHdpZWRlcnVtIG51ciBwb3NpdGl2ZSBXZXJ0ZSBlcnNpY2h0bGljaC4gRWluZSBBdXN3ZXJ0dW5nIGRpZXNlciBnZXBsb3R0ZXRlbiBXZXJ0ZSBlcmdpYnQsIGRhc3Mgc2VociB3ZW5pZ2UgV2VydGUgw7xiZXIgMC4zIGxpZWdlbi4gRGllIMOEaG5saWNoa2VpdCBkaWVzZXIgZXJzdGVuIDEwIEZpbG1lIGdlZ2Vuw7xiZXIgZGVuIGVyc3RlbiAxMDAgYW5kZXJlbiBJdGVtcyBpc3QgYWxzbyBlaGVyIGdlcmluZy4KCiMjIDQuMiBWZXJnbGVpY2hlIGRlaW5lIEltcGxlbWVudGllcnVuZyBkZXIgQ29zaW5lLWJhc2llcnRlbgrDhGhubGljaGtlaXRzbWF0cml4IGbDvHIgb3JkaW5hbGUgUmF0aW5ncyBtaXQgZGVyIHZpYSByZWNvbW1lbmRlcmxhYgp1bmQgZWluZW0gYW5kZXJlbiBSLVBha2V0IGVyemV1Z3RlbiDDhGhubGljaGtlaXRzbWF0cml4LAoKIyMjIDQuMi4xIFZlcmdsZWljaCBDb3NpbmUgU2ltaWxpYXJ0eSBtaXQgUmVjb21tZW5kZXJsYWIKYGBge3J9CiNyZWNvbV9zaW1jb3Npbl80IDwtIGFzLm1hdHJpeChzaW1pbGFyaXR5KG5vcm1hbGl6ZShNb3ZpZUxlbnNlWzE6bnVtYmVyX3VzZXIsIDE6bnVtYmVyX2l0ZW1dKSwgd2hpY2ggPSAiaXRlbXMiLCBtZXRob2QgPSAiY29zaW5lIikpCnJlY29tX3NpbWNvc2luXzQgPC0gYXMubWF0cml4KHNpbWlsYXJpdHkoTW92aWVMZW5zZVsxOm51bWJlcl91c2VyLCAxOm51bWJlcl9pdGVtXSwgd2hpY2ggPSAiaXRlbXMiLCBtZXRob2QgPSAiY29zaW5lIikpCgpyZWNvbV9zaW1jb3Npbl80WzE6NSwxOjVdCmBgYAoKYGBge3J9CnJlc3VsdF9jb3NzaW1fNF9zY2FsZWQgPC0gMSAvIDIgKiAocmVzdWx0X2Nvc3NpbV80ICsgMSkKCnJlc3VsdF9jb3NzaW1fNF9zY2FsZWRbMTo1LDE6NV0KYGBgCgojIyMgNC4yLjIgVmVyZ2xlaWNoIENvc2luZSBTaW1pbGlhcml0eSBtaXQgYW5kZXJlbSBSLVBha2V0CmBgYHtyfQpsaWJyYXJ5KGxzYSkKCnJlY19zaW1NYXQgPC0gc2ltaWxhcml0eShNb3ZpZUxlbnNlQ29tcGFjdF8xWywxOjVdLCB3aGljaCA9ICJpdGVtcyIpCnJlY19zaW1NYXQKCiMgc2ltTWF0X2xzYSA8LSBjb3NpbmUoRGZmb3JTaW1NYXRyaXgsIHkgPSBOVUxMKQpgYGAKCiMjIDQuMyBWZXJnbGVpY2hlIGRlaW5lIG1pdHRlbHMgQ29zaW5lIFNpbWlsYXJpdHkgZXJ6ZXVndGVuIMOEaG5saWNoa2VpdHNtYXRyaXggZsO8ciBvcmRpbmFsZSBSYXRpbmdzIG1pdCBkZXIgSmFjY2FyZC1iYXNpZXJ0ZW4gw4RobmxpY2hrZWl0c21hdHJpeCBmw7xyIGJpbsOkcmUgUmF0aW5ncy4KCgojIDUgQW5hbHlzZSBUb3AtTiBMaXN0ZW4gLSBJQkNGIHZzIFVCQ0YKQXVmZ2FiZSA1OiBWZXJnbGVpY2hlIHVuZCBkaXNrdXRpZXJlIFRvcC1OIEVtcGZlaGx1bmdlbiB2b24gSUJDRgp1bmQgVUJDRiBNb2RlbGxlbiBtaXQgMzAgTmFjaGJhcm4gdW5kIENvc2luZSBTaW1pbGFyaXR5IGbDvHIgZGVuCnJlZHV6aWVydGVuIERhdGVuc2F0ei4KIyMgNS4xIEJlcmVjaG5lIFRvcC0xNSBFbXBmZWhsdW5nZW4gZsO8ciBUZXN0a3VuZGVuIG1pdCBJQkNGIHVuZCBVQkNGIAojIyMgNS4xLjEgcmliY2YgJiBydWJjZiBNb2RlbGwgdHJhaW5pZXJlbgpgYGB7cn0KcmliY2ZfMSA8LSBSZWNvbW1lbmRlcih0cmFpbmluZ18xLCAiSUJDRiIsIHBhcmFtPWxpc3Qoaz0gMzAsIG1ldGhvZCA9ICJjb3NpbmUiKSkKcmliY2ZfMQoKcnViY2ZfMSA8LSBSZWNvbW1lbmRlcih0cmFpbmluZ18xLCAiVUJDRiIsIHBhcmFtPWxpc3Qobm49IDMwLCBtZXRob2QgPSAiY29zaW5lIikpCnJ1YmNmXzEKYGBgCgpgYGB7cn0KcmliY2ZfMiA8LSBSZWNvbW1lbmRlcih0cmFpbmluZ18yLCAiSUJDRiIsIHBhcmFtPWxpc3Qoaz0gMzAsIG1ldGhvZCA9ICJjb3NpbmUiKSkKcmliY2ZfMgoKcnViY2ZfMiA8LSBSZWNvbW1lbmRlcih0cmFpbmluZ18yLCAiVUJDRiIsIHBhcmFtPWxpc3Qobm49IDMwLCBtZXRob2QgPSAiY29zaW5lIikpCnJ1YmNmXzIKYGBgCkVzIHd1cmRlbiBmw7xyIGJlaWRlIHJlZHV6aWVydGVuIERhdGVuc8OkdHplIGpld2VpbHMgZWluIGliY2YgdW5kIHViY2YgUmVjb21tZW5kZXIgZXJzdGVsbHQuIAoKIyMjIDUuMS4yIE1vZGVsIFByZWRpY2l0aW9ucyBlcnN0ZWxsZW4KYGBge3J9CnJpYmNmdG9wTkxpc3RfMSA8LSBwcmVkaWN0KHJpYmNmXzEsIHRlc3RfMSwgbj0xNSkKcmliY2Z0b3BOTGlzdF8xCgpydWJjZnRvcE5MaXN0XzEgPC0gcHJlZGljdChydWJjZl8xLCB0ZXN0XzEsIG49MTUpCnJ1YmNmdG9wTkxpc3RfMQoKcmliY2Z0b3BOTGlzdF8yIDwtIHByZWRpY3QocmliY2ZfMiwgdGVzdF8yLCBuPTE1KQpyaWJjZnRvcE5MaXN0XzIKCnJ1YmNmdG9wTkxpc3RfMiA8LSBwcmVkaWN0KHJ1YmNmXzIsIHRlc3RfMiwgbj0xNSkKcnViY2Z0b3BOTGlzdF8yCmBgYAoKTnVuIHd1cmRlbiBmw7xyIGJlaWRlIERhdGVuc8OkdHplIFByZWRpY3Rpb25zIG1pdCBuID0gMTUgdW5kIGbDvHIgODAgVXNlciBiZXJlY2huZXQuCgojIyMgNS4xLjMgQXVzZ2FiZSB2b24gZWluZXIgUHJlZGljdGlvbgpgYGB7cn0KIyBhdXNnYWJlIHZvbiBlaW5lbSBvdXRwdXQKYXMocmliY2Z0b3BOTGlzdF8xLCAibGlzdCIpWzE6NV0KYGBgCgpEaWVzIGlzdCBlaW5lIMOcYmVyc2ljaHQgZGVyIEVtcGZlaGx1bmdlbiBmw7xyIGRpZSBlcnN0ZW4gNSBVc2VyLiBXaWUgZXJmb3JkZXJ0LCB3dXJkZW4gamV3ZWlscyAxNSBFbXBmZWhsdW5nZW4gZ2VuZXJpZXJ0LiBBdWYgZGVuIGVyc3RlbiBCbGljayB3ZXJkZW4gdmllbGUgdW50ZXJzY2hpZWRsaWNoZW4gRmlsbWUgZW1wZm9obGVuLgoKIyMgNS4yIFZlcmdsZWljaGUgZGllIFRvcC0xNSBFbXBmZWhsdW5nZW4gdW5kIGRlcmVuIFZlcnRlaWx1bmcgdW5kIGRpc2t1dGllcmUgR2VtZWluc2Fta2VpdGVuIHVuZCBVbnRlcnNjaGllZGUgendpc2NoZW4gSUJDRiB1bmQgVUJDRiBmw7xyIGFsbGUgVGVzdGt1bmRlbi4KCmBgYHtyfQojIGRmIGZ1bmt0aW9uIGVyc3RlbGxlbgp0b3BOX2RmIDwtIGZ1bmN0aW9uKHRvcE5MaXN0KXsKICBjb3VudHMgPC0gdGFibGUodW5saXN0KGFzLmFycmF5KGFzKHRvcE5MaXN0LCAibGlzdCIpKSkpCiAgZGYgPC0gZGF0YS5mcmFtZShNb3ZpZSA9IG5hbWVzKGNvdW50cyksIENvdW50ID0gdW5uYW1lKGNvdW50cykpICU+JQogICAgc2VsZWN0KCJNb3ZpZSIsICJDb3VudC5GcmVxIikgJT4lCiAgICByZW5hbWUoIkNvdW50IiA9ICJDb3VudC5GcmVxIikgJT4lCiAgICBhcnJhbmdlKGRlc2MoQ291bnQpKSAgCiAgZGYKfQoKIyBhbGxlIGRmcyBlcnN0ZWxsZW4KcmliY2Z0b3BOX2RmXzEgPC0gdG9wTl9kZihyaWJjZnRvcE5MaXN0XzEpCnJpYmNmdG9wTl9kZl8xCnJpYmNmdG9wTl9kZl8yIDwtIHRvcE5fZGYocmliY2Z0b3BOTGlzdF8yKQpyaWJjZnRvcE5fZGZfMgoKcnViY2Z0b3BOX2RmXzEgPC0gdG9wTl9kZihydWJjZnRvcE5MaXN0XzEpCnJ1YmNmdG9wTl9kZl8xCnJ1YmNmdG9wTl9kZl8yIDwtIHRvcE5fZGYocnViY2Z0b3BOTGlzdF8yKQpydWJjZnRvcE5fZGZfMgoKYGBgCgpEaWUgZXJzdGVuIGJlaWRlbiBUYWJlbGxlbiBzdGVsbGVuIGRpZSBFbXBmZWhsdW5nZW4gdW5kIGRlcmVuIEFuemFobCBiYXNpZXJlbmQgYXVmIElCQ0YgZsO8ciBkaWUgYmVpZGVuIERhdGVuc8OkdHplIGRhci4gSW4gZGVuIFRvcCAxMCBFbXBmZWhsdW5nZW4gc2luZCBzZWhyIHVudGVyc2NoaWVkbGljaGUgRW1wZmVobHVuZ2VuLCBlcyBnaWJ0IGthdW0gw5xiZXJzY2huZWlkdW5nZW4uIEbDvHIgZGVuIGVyc3RlbiBEYXRlbnNhdHogd2lyZCBlaW4gRmlsbSBtYXhpbWFsIDExIG1hbCwgaW0gendlaXRlbiBtYXhpbWFsIDE1IG1hbCBlbXBmb2hsZW4uIEJlaW0gZXJzdGVuIERhdGVuc2F0eiB3ZXJkZW4gaW5zZ2VzYW10IDQ4NyBGaWxtZSB1bmQgYmVpbSB6d2VpdGVuIDQwNyBlbXBmb2hsZW4uCgpEaWUgbGV0enRlbiBiZWlkZW4gVGFiZWxsZW4gc3RlbGxlbiBkaWUgRW1wZmVobHVuZ2VuIGJhc2llcmVuZCBhdWYgVUJDRiBmw7xyIGRpZSBiZWlkZW4gRGF0ZW5zw6R0emUgZGFyLiBEaWUgVG9wIDEwIEZpbG1lIHNpbmQgd2llZGVyIHNlaHIgdW50ZXJzY2hpZWRsaWNoLiBHcm9zc2UgVW50ZXJzY2hpZWRlIGdpYnQgZXMgYXVjaCBiZWkgZGVyIEFuemFobCBWb3Jrb21tZW4gZGVyIFRvcCBGaWxtZS4gRsO8ciBkZW4gZXJzdGVuIERhdGVuc2F0eiB3ZXJkZW4gc2llIGJpcyB6dSAzMCBtYWwgZW1wZm9obGVuLCB3w6RocmVuZCBlcyBiZWltIHp3ZWl0ZW4gbWF4aW1hbCAxNCBtYWwgd2FyLiBBdWNoIGxpZWd0IGRpZSBBbnphaGwgRW1wZmVobHVuZ2VuIG1pdCAzMDEgdnMgMzkyIHdlaXQgYXVzZWluYW5kZXIuCgpGw7xyIHdlaXRlcmUgSW5mb3JtYXRpb25lbiB2aXN1YWxpc2llcmVuIHdpciBudW4gYXVjaCBkaWUgVG9wIEVtcGZlaGx1bmdlbi4KCiMjIyA1LjIuMSBWZXJ0ZWlsdW5nZW4gdmlzdWFsaXNpZXJlbgpgYGB7ciwgZmlnLmhlaWdodD04LCBmaWcud2lkdGg9MTV9CiMgZnVua3Rpb24genVyIFZpc3VhbGlzaWVydW5nCnRvcDE1X2RmX3Zpc3VhbGl6ZSA8LSBmdW5jdGlvbih0b3BOTGlzdCwgc3VidGl0bGUpewogIHRvcE5MaXN0ICU+JSBoZWFkKDE1KSAlPiUgCiAgICBnZ3Bsb3QoYWVzKHggPSByZW9yZGVyKE1vdmllLCBDb3VudCksIHkgPSBDb3VudCkpICsKICAgIGdlb21fYmFyKHN0YXQgPSAiaWRlbnRpdHkiLCBmaWxsID0gImxpbWVncmVlbiIsIGFscGhhID0gMC41LCBjb2xvciA9ICJibGFjayIpICsKICAgIGNvb3JkX2ZsaXAoKSArCiAgICBsYWJzKHggPSAiTW92aWUiLCAKICAgICAgICAgeSA9ICJBbnphaGwiLCAKICAgICAgICAgdGl0bGUgPSAiVG9wLTE1IEVtcGZlaGx1bmdlbiIsCiAgICAgICAgIHN1YnRpdGxlID0gc3VidGl0bGUpCn0KCmdyaWQuYXJyYW5nZSh0b3AxNV9kZl92aXN1YWxpemUocmliY2Z0b3BOX2RmXzEsICJyaWJjZiAxIiksCiAgICAgICAgICAgICB0b3AxNV9kZl92aXN1YWxpemUocnViY2Z0b3BOX2RmXzEsICJydWJjZiAxIiksCiAgICAgICAgICAgICBuY29sID0gMikKCgpncmlkLmFycmFuZ2UodG9wMTVfZGZfdmlzdWFsaXplKHJpYmNmdG9wTl9kZl8yLCAicmliY2YgMiIpLAogICAgICAgICAgICAgdG9wMTVfZGZfdmlzdWFsaXplKHJ1YmNmdG9wTl9kZl8yLCAicnViY2YgMiIpLAogICAgICAgICAgICAgbmNvbCA9IDIpCgpgYGAKRGFuayBkZXIgbGlicmFyeSBncmlkRXh0cmEga8O2bm5lbiB3aXIgZGllIGJlaWRlbiBEYXRlbnPDpHR6ZSBuZWJlbmVpbmFuZGVyIGRhcnN0ZWxsZW4uIEVyc2ljaHRsaWNoIHdpcmQsIHdpZSBzY2huZWxsIGRpZSBBbnphaGwgRW1wZmVobHVuZ2VuIHBybyBGaWxtIGFibmltbXQuIEluIGRlciBlcnN0ZW4gTGFzY2hlLCBJQkNGLCBzaWVodCBtYW4sIGRhc3MgZGllIEFuemFobCBsaW5lYXIgYWJuaW1tdCwgbmFjaGRlbSBkaWUgZXJzdGVuIGbDvG5mIEZpbG1lIGdsZWljaCBow6R1ZmlnIGVtcGZvaGxlbiB3ZXJkZW4uIEhpbmdlZ2VuIG5laG1lbiBkaWUgQW56YWhsIGltIHp3ZWl0ZW4gRGF0ZW5zYXR6IChHcmFmaWsgcmVjaHRzKSB6dWVyc3Qgc2NobmVsbCwgYmlzIGV0d2EgenVtIE5pdmVhdSBkZXMgZXJzdGVuIERhdGVuc2F0emVzLCBkYW5uIGxpbmVhciBhYi4gQmVpIFVCQ0YsIGluIGRlciB6d2VpdGVuIExhc2NoZSwgbmltbXQgZGllIEFuemFobCBiZWkgYmVpZGVuIERhdGVuc8OkdHplbiBsaW5lYXIgYWIuCgpEaWUgZXJ3w6RobnRlIEJlaGF1cHR1bmcg4oCcUmVjb21tZW5kZXIgU3lzdGVtZSBtYWNoZW4gZsO8ciBhbGxlIE51dHplciBkaWUgZ2xlaWNoZW4gRW1wZmVobHVuZ2Vu4oCdIGthbm4gZGFuayBkZXIgVGFiZWxsZW4gdW5kIEhpc3RvZ3JhbW1lIHZlcndvcmZlbiB3ZXJkZW4uIEVzIHdlcmRlbiB2aWVsZSB1bnRlcnNjaGllZGxpY2hlIEZpbG1lIGVtcGZvaGxlbiwgdmllbGV2aWVsZSBGaWxtZSB3ZXJkZW4gbnVyIHdlbmlnZW4gVXNlcm4gKDw0KSBlbXBmb2hsZW4uCgojIDYgQW5hbHlzZSBUb3AtTiBMaXN0ZW4gLSBSYXRpbmdzCkF1ZmdhYmUgNjogVW50ZXJzdWNoZSBkZW4gRWluZmx1c3Mgdm9uIFJhdGluZ3MgKG9yZGluYWxlIHZzIGJpbsOkcmUgUmF0aW5ncykgdW5kIE1vZGVsbHR5cCAoSUJDRiB2cyBVQkNGKSBhdWYgVG9wLU4gRW1wZmVobHVuZ2VuIGbDvHIgZGVuIHJlZHV6aWVydGVuIERhdGVuc2F0ei4gVmVyZ2xlaWNoZSBkZW4gQW50ZWlsIMO8YmVyZWluc3RpbW1lbmRlciBFbXBmZWhsdW5nZW4gZGVyIFRvcC0xNSBMaXN0ZSBmw7xyCiMjIDYuMSBJQkNGIHZzIFVCQ0YsIGJlaWRlIG1pdCBvcmRpbmFsZW0gUmF0aW5nIHVuZCBDb3NpbmUgU2ltaWxhcml0eSBmw7xyIGFsbGUgVGVzdGt1bmRlbiwKYGBge3J9CmNvbXBhcmVfaWJjZl91YmNmIDwtIGZ1bmN0aW9uKGliY2YsIHViY2YpIHsKICBwcmludChwYXN0ZSgiQW56YWhsIElCQ0Y6IiwgbnJvdyhpYmNmKSkpCiAgcHJpbnQocGFzdGUoIkFuemFobCBVQkNGOiIsIG5yb3codWJjZikpKQoKICBJbnRlcnNlY3RvcmRSYXRDb3NpbmUgPC0gaW50ZXJzZWN0KGliY2YkTW92aWUsIHViY2YkTW92aWUpCgogIHByaW50KHBhc3RlKCJBbnphaGwgZ2VtZWluc2FtZSBFbXBmZWhsdW5nZW46IiwgbGVuZ3RoKEludGVyc2VjdG9yZFJhdENvc2luZSkpKQogIHByaW50KHBhc3RlKCJBbnRlaWwgSUJDRjoiLCBsZW5ndGgoSW50ZXJzZWN0b3JkUmF0Q29zaW5lKSAvIG5yb3coaWJjZikgKiAxMDApKQogIHByaW50KHBhc3RlKCJBbnRlaWwgVUJDRjoiLCBsZW5ndGgoSW50ZXJzZWN0b3JkUmF0Q29zaW5lKSAvIG5yb3codWJjZikgKiAxMDApKQp9CgpwcmludCgiRXJzdGUgRGF0ZW5yZWR1a3Rpb24iKQpjb21wYXJlX2liY2ZfdWJjZihyaWJjZnRvcE5fZGZfMSwgcnViY2Z0b3BOX2RmXzEpCnByaW50KCJad2VpdGUgRGF0ZW5yZWR1a3Rpb24iKQpjb21wYXJlX2liY2ZfdWJjZihyaWJjZnRvcE5fZGZfMiwgcnViY2Z0b3BOX2RmXzIpCmBgYAoKRXJzdGUgRGF0ZW5yZWR1a3Rpb246IEbDvHIgSUJDRiB3ZXJkZW4gNDg3IHVuZCBVQkNGIDMwMSBGaWxtZSBlbXBmb2hsZW4sIGRhYmVpIGdpYnQgZXMgZWluZSDDnGJlcmVpbnN0aW1tdW5nIHZvbiAyMzEgRmlsbWVuLgpEYXMgZW50c3ByZWNoZW4gYmVpIElCQ0YgNDcuNSUgdW5kIGJlaSBVQkNGIDc2LjclLgpad2VpdGUgRGF0ZW5yZWR1a3Rpb246IEbDvHIgSUJDRiB3ZXJkZW4gNDA3IHVuZCBVQkNGIDM5MiBGaWxtZSBlbXBmb2hsZW4sIGRhYmVpIGdpYnQgZXMgZWluZSDDnGJlcmVpbnN0aW1tdW5nIHZvbiAyMjYgRmlsbWVuLgpEYXMgZW50c3ByZWNoZW4gYmVpIElCQ0YgNTUlIHVuZCBiZWkgVUJDRiA1NyUuCgpJbnNnZXNhbXQgZ2VuZXJpZXJlbiBhbHNvIGJlaWRlIE1ldGhvZGVuIMOkaG5saWNoZSBFbXBmZWhsdW5nZW4sIHJ1bmQgZGllIEjDpGxmdGUgYmlzIDMvNCBkZXIgRW1wZmVobHVuZ2VuIGdlbmVyaWVydCBhdWNoIGRpZSBhbmRlcmUgTWV0aG9kZS4gQXVmZsOkbGxpZyBpc3QgaGluZ2VnZW4gYmVpbSBlcnN0ZW4gRGF0ZW5zYXR6LCBkYXNzIElCQ0YgdmllbCBtZWhyIEZpbG1lIGVtcGZpZWhsdCwgd8OkaHJlbmQgZXMgYmVpbSB6d2VpdGVuIGV0d2EgZ2xlaWNoIHZpZWwgc2luZC4KCkJlaW0gendlaXRlbiBEYXRlbnNhdHogaXN0IGF1Y2ggZGVyIEFudGVpbCBhbiBHZW1laW5zYW1rZWl0ZW4gamV3ZWlscyBiZWkgcnVuZCA1NSUgdW5kIGRhbWl0IGF1c2dlZ2xpY2hlbmVyIGFscyBpbSBlcnN0ZW4gRGF0ZW5zYXR6LiBJY2gga2FubiBtaXIgdm9yc3RlbGxlbiwgZGFzcyBkYXMgZGFyYW4gbGllZ3QsIGRhc3MgYmVpbSB6d2VpdGVuIERhdGVuc2F0eiBkaWUgU3BhcnNpdHkgZGVyIE1hdHJpeCBow7ZoZXIgaXN0IHVuZCBkYW1pdCBtZWhyIFNwaWVscmF1bSBvZmZlbiBpc3QuCgojIyA2LjIgSUJDRiB2cyBVQkNGLCBiZWlkZSBtaXQgYmluw6RyZW0gUmF0aW5nIHVuZCBKYWNjYXJkIFNpbWlsYXJpdHkgZsO8ciBhbGxlIFRlc3RrdW5kZW4sCmBgYHtyfQp0cmFpbmluZ19iaW5fMSA8LSBiaW5hcml6ZSh0cmFpbmluZ18xLCBtaW5SYXRpbmcgPSA0KQp0ZXN0X2Jpbl8xIDwtIGJpbmFyaXplKHRlc3RfMSwgbWluUmF0aW5nID0gNCkKCnRyYWluaW5nX2Jpbl8yIDwtIGJpbmFyaXplKHRyYWluaW5nXzIsIG1pblJhdGluZyA9IDQpCnRlc3RfYmluXzIgPC0gYmluYXJpemUodGVzdF8yLCBtaW5SYXRpbmcgPSA0KQoKcmliY2ZfYmluXzEgPC0gUmVjb21tZW5kZXIodHJhaW5pbmdfYmluXzEsICJJQkNGIiwgcGFyYW09bGlzdChrPSAzMCwgbWV0aG9kID0gImphY2NhcmQiKSkKcmliY2ZfYmluXzEKCnJ1YmNmX2Jpbl8xIDwtIFJlY29tbWVuZGVyKHRyYWluaW5nX2Jpbl8xLCAiVUJDRiIsIHBhcmFtPWxpc3Qobm49IDMwLCBtZXRob2QgPSAiamFjY2FyZCIpKQpydWJjZl9iaW5fMQoKcmliY2ZfYmluXzIgPC0gUmVjb21tZW5kZXIodHJhaW5pbmdfYmluXzIsICJJQkNGIiwgcGFyYW09bGlzdChrPSAzMCwgbWV0aG9kID0gImphY2NhcmQiKSkKcmliY2ZfYmluXzIKCnJ1YmNmX2Jpbl8yIDwtIFJlY29tbWVuZGVyKHRyYWluaW5nX2Jpbl8yLCAiVUJDRiIsIHBhcmFtPWxpc3Qobm49IDMwLCBtZXRob2QgPSAiamFjY2FyZCIpKQpydWJjZl9iaW5fMgoKYGBgCgpgYGB7cn0KcmliY2Z0b3BOTGlzdF9iaW5fMSA9IHByZWRpY3QocmliY2ZfYmluXzEsIHRlc3RfYmluXzEsIG49MTUpCnJpYmNmdG9wTkxpc3RfYmluXzEKCnJ1YmNmdG9wTkxpc3RfYmluXzEgPSBwcmVkaWN0KHJ1YmNmX2Jpbl8xLCB0ZXN0X2Jpbl8xLCBuPTE1KQpydWJjZnRvcE5MaXN0X2Jpbl8xCgpyaWJjZnRvcE5MaXN0X2Jpbl8yID0gcHJlZGljdChyaWJjZl9iaW5fMiwgdGVzdF9iaW5fMiwgbj0xNSkKcmliY2Z0b3BOTGlzdF9iaW5fMgoKcnViY2Z0b3BOTGlzdF9iaW5fMiA9IHByZWRpY3QocnViY2ZfYmluXzIsIHRlc3RfYmluXzIsIG49MTUpCnJ1YmNmdG9wTkxpc3RfYmluXzIKYGBgCgpgYGB7cn0KcmliY2Z0b3BOX2RmX2Jpbl8xIDwtIHRvcE5fZGYocmliY2Z0b3BOTGlzdF9iaW5fMSkKcmliY2Z0b3BOX2RmX2Jpbl8xCgpyaWJjZnRvcE5fZGZfYmluXzIgPC0gdG9wTl9kZihyaWJjZnRvcE5MaXN0X2Jpbl8yKQpyaWJjZnRvcE5fZGZfYmluXzIKCnJ1YmNmdG9wTl9kZl9iaW5fMSA8LSB0b3BOX2RmKHJ1YmNmdG9wTkxpc3RfYmluXzEpCnJ1YmNmdG9wTl9kZl9iaW5fMQoKcnViY2Z0b3BOX2RmX2Jpbl8yIDwtIHRvcE5fZGYocnViY2Z0b3BOTGlzdF9iaW5fMikKcnViY2Z0b3BOX2RmX2Jpbl8yCmBgYAoKRGllc2UgQXVzd2VydHVuZyBlbnRzcHJpY2h0IGRlciwgZGVyIHZvcmhlcmlnZW4gQXVmZ2FiZSwgbnVyIGRhc3MgZGllc2VzIG1hbCBtaXQgYmluw6RyZW4gUmF0aW5ncyB1bmQgSmFjY2FyZCBTaW1pbGFyaXR5IGdlYXJiZWl0ZXQgd3VyZGUuCkVzIHdpcmQgYXVjaCBoaWVyIGVyc2ljaHRsaWNoLCBkYXNzIGRpZSBFbXBmZWhsdW5nZW4gc2VociB1bnRlcnNjaGllZGxpY2ggc2luZC4gQmVpIElCQ0YgKGVyc3RlIHp3ZWkgVGFiZWxsZW4pIHdlcmRlbiBmw7xyIGRlbiBlcnN0ZW4gRGF0ZW5zYXR6IGRpZSBUb3AgRmlsbWUgc2VociB2aWVsIGjDpHVmaWdlciAoMzkgbWFsIHZzIDE2IG1hbCkgZW1wZm9obGVuLiBEYXMgZ2xlaWNoZSBNdXN0ZXIsIHdlbm4gYWJlciBzY2h3w6RjaGVyLCBpc3QgYmVpIGRlbiBVQkNGIGVyc2ljaHRsaWNoLgoKYGBge3J9CnByaW50KCJFcnN0ZSBEYXRlbnJlZHVrdGlvbiBiaW5hZXIiKQpjb21wYXJlX2liY2ZfdWJjZihyaWJjZnRvcE5fZGZfYmluXzEsIHJ1YmNmdG9wTl9kZl9iaW5fMSkKcHJpbnQoIlp3ZWl0ZSBEYXRlbnJlZHVrdGlvbiBiaW5hZXIiKQpjb21wYXJlX2liY2ZfdWJjZihyaWJjZnRvcE5fZGZfYmluXzIsIHJ1YmNmdG9wTl9kZl9iaW5fMikKYGBgCkltIEdlZ2Vuc2F0eiB6dXIgdm9yaGVyaWdlbiBBdWZnYWJlIHVuZCBkZW4gendlaXRlbiBEYXRlbnNhdHosIGdpYnQgZXMgZsO8ciBkZW4gZXJzdGVuIGZhc3Qga2VpbmUgZ2VtZWluc2FtZSBFbXBmZWhsdW5nZW4uIEVzIGbDpGxsdCBhdWNoIGF1ZiwgZGFzcyBmw7xyIElCQ0YgbnVyIDg3IEZpbG1lIGVtcGZvaGxlbiB3ZXJkZW4uIERpZXNlIEF1c3dlcnR1bmcgd3VyZGUgbWl0IG1pblJhdGluZyA0IGbDvHIgZGllIGJpbsOkcmUgS2xhc3NpZml6aWVydW5nIGJlcmVjaG5ldC4gTWl0IFJhdGluZyAzIHNpZWh0IGRpZXNlciBTYWNodmVyaGFsdCDDpGhubGljaCBhdXMsIGJlaSBtaW5SYXRpbmcgNSBpc3QgZGllIMOcYmVyZWluc3RpbW11bmcgYWJlciB3aWVkZXIgaW0gbm9ybWFsZW4gQmVyZWljaC4gV2llc28gbWluUmF0aW5nIDMgdW5kIDQgc28gdGllZmUgw5xiZXJlaW5zdGltbXVuZ2VuIGdlbmVyaWVydCBoYWJlbiwga8O2bm5lbiB3aXIgbmljaHQgbmFjaHZvbGx6aWVoZS4gRGFzcyBtaW5SYXRpbmcgNSBhYmVyIGJlc3NlcmUgUmVzdWx0YXRlIGdlbmVyaWVydCwgbGllZ3QgZGFyYW4sIGRhc3MgbnVuIG51ciBub2NoIHdlbmlnZSBJdGVtcyBhbHMgMSBrbGFzc2lmaXppZXJ0IHdlcmRlbiB1bmQgZGFtaXQgd2VuaWdlciBGaWxtZSB6dXIgRW1wZmVobHVuZyB6dXIgVmVyZsO8Z3VuZyBzdGVsbGVuLgoKCiMjIDYuMyBVQkNGIG1pdCBvcmRpbmFsZW0gKENvc2luZSBTaW1pbGFyaXR5KSB2cyBVQkNGIG1pdCBiaW7DpHJlbSBSYXRpbmcgKEphY2NhcmQgU2ltaWxhcml0eSkgZsO8ciBhbGxlIFRlc3RrdW5kZW4uCgpgYGB7cn0KY29tcGFyZV91YmNmIDwtIGZ1bmN0aW9uKGliY2YsIHViY2YpIHsKICBwcmludChwYXN0ZSgiQW56YWhsIFVCQ0Ygb3JkOiIsIG5yb3coaWJjZikpKQogIHByaW50KHBhc3RlKCJBbnphaGwgVUJDRiBiaW46IiwgbnJvdyh1YmNmKSkpCgogIEludGVyc2VjdG9yZFJhdENvc2luZSA8LSBpbnRlcnNlY3QoaWJjZiRNb3ZpZSwgdWJjZiRNb3ZpZSkKCiAgcHJpbnQocGFzdGUoIkFuemFobCBnZW1laW5zYW1lIEVtcGZlaGx1bmdlbjoiLCBsZW5ndGgoSW50ZXJzZWN0b3JkUmF0Q29zaW5lKSkpCiAgcHJpbnQocGFzdGUoIkFudGVpbCBVQkNGIG9yZDoiLCBsZW5ndGgoSW50ZXJzZWN0b3JkUmF0Q29zaW5lKSAvIG5yb3coaWJjZikgKiAxMDApKQogIHByaW50KHBhc3RlKCJBbnRlaWwgVUJDRiBiaW46IiwgbGVuZ3RoKEludGVyc2VjdG9yZFJhdENvc2luZSkgLyBucm93KHViY2YpICogMTAwKSkKfQpgYGAKCkVyc3RlbGx1bmcgZGVyIEZ1bmt0aW9uIHVuZCBCZXJlY2hudW5nIGRlcyBSZXN1bHRhdHMKCmBgYHtyfQpwcmludCgiRXJzdGUgRGF0ZW5yZWR1a3Rpb24iKQpjb21wYXJlX3ViY2YocnViY2Z0b3BOX2RmXzEsIHJ1YmNmdG9wTl9kZl9iaW5fMSkKcHJpbnQoIlp3ZWl0ZSBEYXRlbnJlZHVrdGlvbiIpCmNvbXBhcmVfdWJjZihydWJjZnRvcE5fZGZfMiwgcnViY2Z0b3BOX2RmX2Jpbl8yKQpgYGAKCkJlaW0gVmVyZ2xlaWNoIHZvbiBVQkNGIG1pdCBvcmRpbmFsZW0gdW5kIGJpbsOkcmVtIFJhdGluZyB3ZXJkZW4gd2llZGVyIG1laHIgw7xiZXJlaW5zdGltbWVuZGUgRmlsbWUgZW1wZm9obGVuLiBGw7xyIGRlbiBlcnN0ZW4gRGF0ZW5zYXR6IHdlcmRlbiAyMDcgRmlsbWUgYmVpIGJlaWRlbiBNb2RlbGxlbiB1bmQgYmVpbSB6d2VpdGVuIERhdGVuc2F0eiAzMDEgw7xiZXJlaW5zdGltbWVuZGUgRmlsbWUgZW1wZm9obGVuLiBEYSBiZWkgYmVpZGVuIERhdGVuc8OkdHplbiBtaXQgb3JkaW5hbGVtIFJhdGluZyB3ZW5pZ2VyIEVtcGZlaGx1bmdlbiBnZW5lcmllcnQgd2VyZGVuLCBpc3QgZGVyIEFudGVpbCDDnGJlcmVpbnN0aW1tdW5nZW4gYmVpIG9yZGluYWxlbiBSYXRpbmdzIGVudHNwcmVjaGVuZCBow7ZoZXIuCgojIDcgQW5hbHlzZSBUb3AtTiBMaXN0ZW4gLSBJQkNGIHZzIFNWRApBdWZnYWJlIDc6IFZlcmdsZWljaGUKTWVtb3J5LWJhc2VkIElCQ0YgdW5kIE1vZGVsbC1iYXNlZCBTVkQgUmVjb21tZW5kZXJzIGJlesO8Z2xpY2ggw5xiZXJzY2huZWlkdW5nIGlocmVyIFRvcC1OIEVtcGZlaGx1bmdlbiBmw7xyIGRpZSBVc2VyLUl0ZW0gTWF0cml4IGRlcyByZWR1emllcnRlbiBEYXRlbnNhdHplcyAoQmFzaXM6IHJlZHV6aWVydGVyIERhdGVuc2F0eiwgSUJDRiBtaXQgMzAgTmFjaGJhcm4gdW5kIENvc2luZSBTaW1pbGFyaXR5KS4KVmVyZ2xlaWNoZSB3aWUgc2ljaCBkZXIgQW50ZWlsIMO8YmVyZWluc3RpbW1lbmRlciBFbXBmZWhsdW5nZW4gZGVyIFRvcC0xNSBMaXN0ZSBmw7xyIElCQ0YgdnMgdmVyc2NoaWVkZW5lIFNWRCBNb2RlbGxlIHZlcsOkbmRlcnQsIHdlbm4gZGllIEFuemFobCBkZXIgU2luZ3Vsw6Ryd2VydGUgZsO8ciBTVkQgdm9uIDEwIGF1ZiAyMCwgMzAsIDQwLCA1MCB2ZXLDpG5kZXJ0IHdpcmQuCmBgYHtyfQojIEZ1bmt0aW9uIGZ1ZXIgU1ZEIE1vZGVsCmdlbmVyYXRlX1NWRF90b3BOX3JlY29tbSA8LSBmdW5jdGlvbih0cmFpbiwgdGVzdCwgc3ZkX3ZhbHVlID0ga3N2ZCl7CglyZWNvbV9tb2RlbCA8LSBSZWNvbW1lbmRlcih0cmFpbiwgIlNWRCIsIHBhcmFtPWxpc3Qoaz0gc3ZkX3ZhbHVlKSkKCXRvcF9uX3JlY29tIDwtIHByZWRpY3QocmVjb21fbW9kZWwsIHRlc3QsIG49MTUpCiAgdG9wX25fcmVjb20KfQoKIyBGdW5rdGlvbiBmdWVyIHZlcnNjaGllZGVuZSBOCmdlbmVyYXRlX1NWRF90b3BOX2xpc3RzIDwtIGZ1bmN0aW9uKHRyYWluLCB0ZXN0LCBOX3ZhbHVlcykgewogIHJzdmRfdG9wTl9saXN0cyA8LSBsaXN0KCkKICBmb3IgKGkgaW4gMTpsZW5ndGgoTl92YWx1ZXMpKSB7CiAgICBOIDwtIE5fdmFsdWVzW2ldCiAgICBsaXN0X25hbWUgPC0gcGFzdGUwKCJyc3ZkIiwgTiwgInRvcE5MaXN0IikKICAgIHJzdmRfdG9wTl9saXN0c1tbbGlzdF9uYW1lXV0gPC0gZ2VuZXJhdGVfU1ZEX3RvcE5fcmVjb21tKHRyYWluLCB0ZXN0LCBOKQogIH0KICByc3ZkX3RvcE5fbGlzdHMKfQpgYGAKCkZ1bmt0aW9uIHp1ciBCZXJlY2hudW5nIGRlcyBSZXN1bHRhdHMKCmBgYHtyfQpOX3ZhbHVlcyA8LSBjKDEwLCAyMCwgMzAsIDQwLCA1MCkKcnN2ZF90b3BOX2xpc3RzXzEgPC0gZ2VuZXJhdGVfU1ZEX3RvcE5fbGlzdHModHJhaW5pbmdfMSwgdGVzdF8xLCBOX3ZhbHVlcykKcHJpbnQoIkVyc3RlciBEYXRlbnNhdHoiKQpyc3ZkX3RvcE5fbGlzdHNfMQoKcnN2ZF90b3BOX2xpc3RzXzIgPC0gZ2VuZXJhdGVfU1ZEX3RvcE5fbGlzdHModHJhaW5pbmdfMiwgdGVzdF8yLCBOX3ZhbHVlcykKcHJpbnQoIlp3ZWl0ZXIgRGF0ZW5zYXR6IikKcnN2ZF90b3BOX2xpc3RzXzIKYGBgCgoKYGBge3J9CmdlbmVyYXRlX3RvcE5fZGZzIDwtIGZ1bmN0aW9uKHJzdmRfdG9wTl9saXN0cykgewogIHRvcE5fZGZzIDwtIGxpc3QoKQogIAogIGZvciAoaSBpbiAxOmxlbmd0aChyc3ZkX3RvcE5fbGlzdHMpKSB7CiAgICBsaXN0X25hbWUgPC0gbmFtZXMocnN2ZF90b3BOX2xpc3RzKVtpXQogICAgZGZfbmFtZSA8LSBwYXN0ZTAobGlzdF9uYW1lLCAiX2RmIikKICAgIHRvcE5fZGZzW1tkZl9uYW1lXV0gPC0gdG9wTl9kZihyc3ZkX3RvcE5fbGlzdHNbW2ldXSkKICB9CiAgCiAgdG9wTl9kZnMKfQoKdG9wTl9kZl9zdmRfMSA8LSBnZW5lcmF0ZV90b3BOX2Rmcyhyc3ZkX3RvcE5fbGlzdHNfMSkKcHJpbnQoIkVyc3RlciBEYXRlbnNhdHoiKQp0b3BOX2RmX3N2ZF8xCgp0b3BOX2RmX3N2ZF8yIDwtIGdlbmVyYXRlX3RvcE5fZGZzKHJzdmRfdG9wTl9saXN0c18yKQpwcmludCgiWndlaXRlciBEYXRlbnNhdHoiKQp0b3BOX2RmX3N2ZF8yCgoKYGBgCgpEaWUgZXJzdGVuIGbDvG5mIFRhYmVsbGVuIHNpbmQgZGllIFJlc3VsdGF0ZSBmw7xyIGRlbiBlcnN0ZW4gRGF0ZW5zYXR6LiBFcyBoYW5kZWx0IHNpY2ggYXVmc3RlaWdlbmQgdW0gZGllIEFuemFobCBTaW5ndWzDpHJ3ZXJ0ZSB2b24gMTAgYmlzIDUwLiBEaWUgbGV0enRlbiBmw7xuZiBUYWJlbGxlbiBiZWluaGFsdGVuIGRhcyBnbGVpY2hlIFJlc3VsdGF0LCBlaW5mYWNoIGbDvHIgZGVuIHp3ZWl0ZW4gRGF0ZW5zYXR6LiBEaWVzZSBBdXN3ZXJ0dW5nIHdpcmQgbm9jaCBuaWNodCBmw7xyIGRpZSBCZWFudHdvcnR1bmcgZGVyIEF1ZmdhYmUgdmVyd2VuZGV0LCBzb25kZXJuIGdhYiB1bnMgZWluZW4gZXJzdGVuIMOcYmVyYmxpY2sgw7xiZXIgZGllIFJlc3VsdGF0ZQoKYGBge3J9CmNvbXBhcmVfaWJjZl9zdmQgPC0gZnVuY3Rpb24ocmliY2YsIHN2ZCwgc3ZkX3ZhbHVlKSB7CiAgaW50ZXJzZWN0IDwtIGludGVyc2VjdChyaWJjZiRNb3ZpZSwgc3ZkJE1vdmllKQogIHByaW50KHBhc3RlKCJBbnphaGwgZ2VtZWluc2FtZSBFbXBmZWhsdW5nZW4gU1ZEIiwgc3ZkX3ZhbHVlLCAiOiIsIGxlbmd0aChpbnRlcnNlY3QpKSkKICBwcmludChwYXN0ZSgiR2VtZWluc2FtZXIgcmVsYXRpdmVyIEFudGVpbCBmw7xyIEFuemFobCBTaW5ndWzDpHJ3ZXJ0ZSIsIHN2ZF92YWx1ZSwgIjoiLCBsZW5ndGgoaW50ZXJzZWN0KSAvIG5yb3cocmliY2YpICogMTAwKSkKfQoKcHJpbnQoIkVyc3RlciBEYXRlbnNhdHoiKQpjb21wYXJlX2liY2Zfc3ZkKHJpYmNmdG9wTl9kZl8xLCB0b3BOX2RmX3N2ZF8xJHJzdmQxMHRvcE5MaXN0X2RmLCAxMCkKY29tcGFyZV9pYmNmX3N2ZChyaWJjZnRvcE5fZGZfMSwgdG9wTl9kZl9zdmRfMSRyc3ZkMjB0b3BOTGlzdF9kZiwgMjApCmNvbXBhcmVfaWJjZl9zdmQocmliY2Z0b3BOX2RmXzEsIHRvcE5fZGZfc3ZkXzEkcnN2ZDMwdG9wTkxpc3RfZGYsIDMwKQpjb21wYXJlX2liY2Zfc3ZkKHJpYmNmdG9wTl9kZl8xLCB0b3BOX2RmX3N2ZF8xJHJzdmQ0MHRvcE5MaXN0X2RmLCA0MCkKY29tcGFyZV9pYmNmX3N2ZChyaWJjZnRvcE5fZGZfMSwgdG9wTl9kZl9zdmRfMSRyc3ZkNTB0b3BOTGlzdF9kZiwgNTApCgpwcmludCgiWndlaXRlciBEYXRlbnNhdHoiKQpjb21wYXJlX2liY2Zfc3ZkKHJpYmNmdG9wTl9kZl8yLCB0b3BOX2RmX3N2ZF8yJHJzdmQxMHRvcE5MaXN0X2RmLCAxMCkKY29tcGFyZV9pYmNmX3N2ZChyaWJjZnRvcE5fZGZfMiwgdG9wTl9kZl9zdmRfMiRyc3ZkMjB0b3BOTGlzdF9kZiwgMjApCmNvbXBhcmVfaWJjZl9zdmQocmliY2Z0b3BOX2RmXzIsIHRvcE5fZGZfc3ZkXzIkcnN2ZDMwdG9wTkxpc3RfZGYsIDMwKQpjb21wYXJlX2liY2Zfc3ZkKHJpYmNmdG9wTl9kZl8yLCB0b3BOX2RmX3N2ZF8yJHJzdmQ0MHRvcE5MaXN0X2RmLCA0MCkKY29tcGFyZV9pYmNmX3N2ZChyaWJjZnRvcE5fZGZfMiwgdG9wTl9kZl9zdmRfMiRyc3ZkNTB0b3BOTGlzdF9kZiwgNTApCmBgYAoKRsO8ciBkZW4gZXJzdGVuIERhdGVuc2F0eiB3ZXJkZW4gYmVpIFNWRCBXZXJ0IDEwIDc2IGdlbWVpbnNhbWUgRW1wZmVobHVuZ2VuIG1pdCBJQkNGIGdlbmVyaWVydC4gRGllcyBlbnRzcHJpY2h0IGVpbmVtIEFudGVpbCB2b24gMTUuNiUgZGVyIEVtcGZlaGx1bmdlbiB2b20gU1ZEIE1vZGVsbC4gQmlzIHp1ciBBbnphaGwgdm9uIDUwIFNpbmd1bMOkcndlcnRlbiBzdGVpZ3QgZGllIEFuemFobCBnZW1laW5zYW1lciBFbXBmZWhsdW5nZW4gYXVmIDExNywgd2FzIGVpbmVtIEFudGVpbCB2b24gMjQlIGVudHNwcmljaHQuIAoKIyA4IEltcGxlbWVudGllcnVuZyBUb3AtTiBNZXRyaWtlbgpBdWZnYWJlIDggKERJWSkgCiMjIDguMSBDb3ZlcmFnZU4gCmBgYHtyfQpyaWJjZl84IDwtIFJlY29tbWVuZGVyKE1vdmllTGVuc2UsICJJQkNGIiwgcGFyYW09bGlzdChrPSAzMCwgbWV0aG9kID0gImNvc2luZSIpKQpyaWJjZl84CgpyaWJjZnRvcE5MaXN0XzggPC0gcHJlZGljdChyaWJjZl84LCBNb3ZpZUxlbnNlLCBuPTE1KQpyaWJjZnRvcE5MaXN0XzgKCmxpc3RfaXRlbXNfOCA8LSB1bmlxdWUodW5saXN0KGFzKHJpYmNmdG9wTkxpc3RfOCwgImxpc3QiKSwgdXNlLm5hbWVzID0gRkFMU0UpKQpsZW5faXRlbXNfOCA8LSBsZW5ndGgobGlzdF9pdGVtc184KQoKbGVuX2FsbF9pdGVtc184IDwtIGRpbShNb3ZpZUxlbnNlKVsyXQpsZW5fYWxsX2l0ZW1zXzgKCmNvdmVyYWdlTiA8LSBsZW5faXRlbXNfOCAvIGxlbl9hbGxfaXRlbXNfOApjb3ZlcmFnZU4KYGBgCjQxLjcgJSBkZXIgdm9yaGFuZGVuZW4gRmlsbWUgd2VyZGVuIGVtcGZvaGxlbi4KCiMjIDguMiBOb3ZlbHR5TgpgYGB7cn0KbnJhdGluZ3MoTW92aWVMZW5zZSkgLyBsZW5fYWxsX2l0ZW1zXzgKYGBgCgojIDkgV2FobCBkZXMgb3B0aW1hbGVuIFJlY29tbWVuZGVycwpBdWZnYWJlIDkKIyMgOS4xIFZlcndlbmRlIGbDvHIgZGllIEV2YWx1aWVydW5nIDEwLWZhY2hlIEtyZXV6dmFsaWRpZXJ1bmcKYGBge3J9CnNldC5zZWVkKDEyMzQpCnNjaGVtZV8xIDwtIGV2YWx1YXRpb25TY2hlbWUoTW92aWVMZW5zZUNvbXBhY3RfMSwgbWV0aG9kPSJjcm9zcy12YWxpZGF0aW9uIiwgayA9IDEwLCBnaXZlbj0zLCBnb29kUmF0aW5nPTUpCnNjaGVtZV8yIDwtIGV2YWx1YXRpb25TY2hlbWUoTW92aWVMZW5zZUNvbXBhY3RfMiwgbWV0aG9kPSJjcm9zcy12YWxpZGF0aW9uIiwgayA9IDEwLCBnaXZlbj0zLCBnb29kUmF0aW5nPTUpCgpwcmludCgiRXJzdGUgRGF0ZW5yZWR1a3Rpb24iKQpzY2hlbWVfMQpwcmludCgiWndlaXRlIERhdGVucmVkdWt0aW9uIikKc2NoZW1lXzIKCgpgYGAKCiMjIDkuMiBCZWdyw7xuZGUgZGVpbmUgV2FobCB2b24gTWV0cmlrZW4gdW5kIE1vZGVsbApgYGB7cn0KYWxnb3JpdGhtcyA8LSBsaXN0KCJoeWJyaWQiID0gbGlzdChuYW1lID0gIkhZQlJJRCIsIHBhcmFtID1saXN0KHJlY29tbWVuZGVycyA9IGxpc3QoU1ZEID0gbGlzdChuYW1lPSJTVkQiLCBwYXJhbT1saXN0KGsgPSA0MCkpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBQT1BVTEFSID0gbGlzdChuYW1lID0gIlBPUFVMQVIiLCBwYXJhbSA9IE5VTEwpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICkpKSwKICAgICAgICAgICAgICAgICAgICJsaWJtZiIgPSBsaXN0KG5hbWU9IkxJQk1GIiwgcGFyYW09bGlzdChkaW09MTApKSwKICAgICAgICAgICAgICAgICAgICJwb3B1bGFyIGl0ZW1zIiA9IGxpc3QobmFtZT0iUE9QVUxBUiIsIHBhcmFtPU5VTEwpLAogICAgICAgICAgICAgICAgICAgInVzZXItYmFzZWQgQ0YiID0gbGlzdChuYW1lPSJVQkNGIiwgcGFyYW09bGlzdChubj01MCkpLAogICAgICAgICAgICAgICAgICAgIml0ZW0tYmFzZWQgQ0YiID0gbGlzdChuYW1lPSJJQkNGIiwgcGFyYW09bGlzdChrPTUwKSksCiAgICAgICAgICAgICAgICAgICAiU1ZENDAiID0gbGlzdChuYW1lPSJTVkQiLCBwYXJhbT1saXN0KGsgPSA0MCkpKQoKcHJpbnQoIkVyc3RlciBEYXRlbnNhdHoiKQpyZXN1bHRzXzEgPC0gZXZhbHVhdGUoc2NoZW1lXzEsIGFsZ29yaXRobXMsIHR5cGUgPSAidG9wTkxpc3QiLCBuPWMoMTAsIDE1LCAyMCwgMjUsIDMwKSkKcHJpbnQoIlp3ZWl0ZXIgRGF0ZW5zYXR6IikKcmVzdWx0c18yIDwtIGV2YWx1YXRlKHNjaGVtZV8yLCBhbGdvcml0aG1zLCB0eXBlID0gInRvcE5MaXN0Iiwgbj1jKDEwLCAxNSwgMjAsIDI1LCAzMCkpCmBgYAoKYGBge3J9CnBsb3QocmVzdWx0c18xLCBhbm5vdGF0ZT1jKDEsMyksIGxlZ2VuZD0idG9wbGVmdCIpCnBsb3QocmVzdWx0c18yLCBhbm5vdGF0ZT1jKDEsMyksIGxlZ2VuZD0idG9wbGVmdCIpCmBgYAoKIyMgOS4zIEFuYWx5c2llcmUgZGFzIGJlc3RlIE1vZGVsbCBmw7xyIFRvcC1OIFJlY29tbWVuZGF0aW9ucyBtaXQgTiA9IDEwLCAxNSwgMjAsIDI1IHVuZCAzMCwKdmllbGVzIGJsYWJhYWxhYmFhYXNzc3MKCiMjIDkuNCBPcHRpbWllcmUgZGVpbiBiZXN0ZXMgTW9kZWxsIGhpbnNpY2h0bGljaCBIeXBlcnBhcmFtZXRlcm4KYGBge3J9CmFsZ29yaXRobXNpbXByb3ZlZHJlY29tIDwtIGxpc3QoInBvcHVsYXIgaXRlbXMgY2VudGVyIiA9IGxpc3QobmFtZT0iUE9QVUxBUiIsIHBhcmFtPU5VTEwpLAogICAgICAgICAgICAgICAgICAgInBvcHVsYXIgaXRlbXMgWi1zY29yZSIgPSBsaXN0KG5hbWU9IlBPUFVMQVIiLCBwYXJhbT1saXN0KG5vcm1hbGl6ZT0iWi1zY29yZSIpKSkKCnJlc3VsdHNpbXByb3ZlZHJlY29tXzEgPC0gZXZhbHVhdGUoc2NoZW1lXzEsIGFsZ29yaXRobXNpbXByb3ZlZHJlY29tLCB0eXBlID0gInRvcE5MaXN0Iiwgbj1jKDEwLCAxNSwgMjAsIDI1LCAzMCkpCnJlc3VsdHNpbXByb3ZlZHJlY29tXzIgPC0gZXZhbHVhdGUoc2NoZW1lXzIsIGFsZ29yaXRobXNpbXByb3ZlZHJlY29tLCB0eXBlID0gInRvcE5MaXN0Iiwgbj1jKDEwLCAxNSwgMjAsIDI1LCAzMCkpCmBgYAoKYGBge3J9CnBsb3QocmVzdWx0c2ltcHJvdmVkcmVjb21fMSwgYW5ub3RhdGU9YygxLDMpLCBsZWdlbmQ9InRvcGxlZnQiKQpwbG90KHJlc3VsdHNpbXByb3ZlZHJlY29tXzIsIGFubm90YXRlPWMoMSwzKSwgbGVnZW5kPSJ0b3BsZWZ0IikKYGBgCgpIaW53ZWlzOiBWZXJ3ZW5kZSBmw7xyIGRlbiBUb3AtTW92aWUgUmVjb21tZW5kZXIgZGllIEZpbG1lIG1pdCBkZW4gaMO2Y2hzdGVuIER1cmNoc2Nobml0dHNyYXRpbmdzLgojIDEwIEltcGxlbWVudGllcnVuZyBUb3AtTiBNb25pdG9yCkF1ZmdhYmUgMTAgKERJWSk6IFVudGVyc3VjaGUgZGllIHJlbGF0aXZlIMOcYmVyZWluc3RpbW11bmcgendpc2NoZW4KVG9wLU4gRW1wZmVobHVuZ2VuIHVuZCBwcsOkZmVyaWVydGVuIEZpbG1lbiBmw7xyIDQgdW50ZXJzY2hpZWRsaWNoZQpNb2RlbGxlICh6LkIuIElCQ0YgdW5kIFVCQ0YgbWl0IHVudGVyc2NoaWVkbGljaGVuIMOEaG5saWNoa2VpdHNtZXRyaWtlbiAvIE5hY2hiYXJzY2hhZnRlbiBzb3dpZSBTVkQgbWl0IHVudGVyc2NoaWVkbGljaGVyCkRpbWVuc2lvbmFsaXTDpHRzcmVkdWt0aW9uKS4KCiMjIDEwLjEgRml4aWVyZSAyMCB6dWbDpGxsaWcgZ2V3w6RobHRlIFRlc3RrdW5kZW4gZsO8ciBhbGxlIE1vZGVsbHZlcmdsZWljaGUsCmBgYHtyfQojIHNlbGVjdCAyMCByYW5kb20gdXNlcnMKc2V0LnNlZWQoMTIzNCkKdGVzdFVzZXJzIDwtIHNhbXBsZSgxOm5yb3coTW92aWVMZW5zZSksIDIwKQp0ZXN0VXNlcnMKCiMgZmlsdGVyIE1vdmllTGVuc2UgYnkgdGVzdFVzZXJzCk1vdmllTGVuc2VUZXN0IDwtIE1vdmllTGVuc2VbdGVzdFVzZXJzLF0gCk1vdmllTGVuc2VUZXN0CmBgYAoKIyMgMTAuMiBCZXN0aW1tZSBkZW4gQW50ZWlsIGRlciBUb3AtTiBFbXBmZWhsdW5nIG5hY2ggR2VucmVzIHBybyBLdW5kZSwKYGBge3J9CiMgZ2V0IGZyb20gZXZlcnkgVGVzdFVzZXJzIHRoZSBUb3BfTiBpdGVtIGxpc3QKcmliY2ZfMTAgPC0gUmVjb21tZW5kZXIoTW92aWVMZW5zZVRlc3QsICJJQkNGIiwgcGFyYW09bGlzdChrPSAzMCwgbWV0aG9kID0gImNvc2luZSIpKQoKIyBwcmVkaWN0IFRvcC1OIGl0ZW1zIGZvciBldmVyeSB1c2VyCnJpYmNmdG9wTkxpc3RfMTAgPC0gcHJlZGljdChyaWJjZl8xMCwgTW92aWVMZW5zZVRlc3QsIG49MTUpCgojIGNyZWF0ZSBhIGxpc3Qgd2l0aCB0aGUgdG9wTiBpdGVtcyBmb3IgZXZlcnkgdXNlcgpyaWJjZnRvcE5MaXN0XzEwX2xpc3QgPC0gYXMocmliY2Z0b3BOTGlzdF8xMCwgImxpc3QiKQoKIyBjcmVhdGUgYSB0aWJibGUgd2l0aCB0aGUgdG9wTiBpdGVtcyBmb3IgZXZlcnkgdXNlcgpyaWJjZnRvcE5MaXN0XzEwX3RpYmJsZSA8LSBhc190aWJibGUocmliY2Z0b3BOTGlzdF8xMF9saXN0KQoKIyB0cmFuc2Zvcm0gdGhlIHRpYmJsZSB0byBhIGRhdGEgZnJhbWUKcmliY2Z0b3BOTGlzdF8xMF9kZiA8LSBhcy5kYXRhLmZyYW1lKHJpYmNmdG9wTkxpc3RfMTBfdGliYmxlKQoKIyByZXBsYWNlIGNvbG5hbWUgd2l0aCB0ZXN0VXNlcnMKY29sbmFtZXMocmliY2Z0b3BOTGlzdF8xMF9kZikgPC0gdGVzdFVzZXJzCgojIHRyYW5zcG9zZSBkYXRhIGZyYW1lCnJpYmNmdG9wTkxpc3RfMTBfZGZfdHJhbnNwb3NlZCA8LSB0KHJpYmNmdG9wTkxpc3RfMTBfZGYpCgojIGNoYW5nZSByaWJjZnRvcE5MaXN0XzEwX2RmX3RyYW5zcG9zZWQgdG8gYSB0aWJibGUKcmliY2Z0b3BOTGlzdF8xMF9kZl90cmFuc3Bvc2VkX3RpYmJsZSA8LSBhc190aWJibGUocmliY2Z0b3BOTGlzdF8xMF9kZl90cmFuc3Bvc2VkKQoKIyBhZGQgYSBjb2x1bW4gd2l0aCB0aGUgdGVzdFVzZXJzCnJpYmNmdG9wTkxpc3RfMTBfZGZfdHJhbnNwb3NlZF90aWJibGUkdGVzdFVzZXJzIDwtIHRlc3RVc2VycwoKIyBwaXZvdCBsb25nZXIgZGF0YWZyYW1lCnJpYmNmdG9wTkxpc3RfMTBfZGZfdHJhbnNwb3NlZF90aWJibGVfcGl2b3QgPC0gcGl2b3RfbG9uZ2VyKHJpYmNmdG9wTkxpc3RfMTBfZGZfdHJhbnNwb3NlZF90aWJibGUsIGNvbHMgPSAxOjE1LCBuYW1lc190byA9ICJ0b3BOIiwgdmFsdWVzX3RvID0gIml0ZW1JRCIpCgojIGdldCBnZW5yZSBmcm9tIGVhY2ggaXRlbQpyaWJjZnRvcE5MaXN0XzEwX2RmX3RyYW5zcG9zZWRfdGliYmxlX3Bpdm90X2dlbnJlIDwtIGxlZnRfam9pbihyaWJjZnRvcE5MaXN0XzEwX2RmX3RyYW5zcG9zZWRfdGliYmxlX3Bpdm90LCBNb3ZpZUxlbnNlTWV0YSwgYnkgPSBjKCJpdGVtSUQiID0gInRpdGxlIikpCnJpYmNmdG9wTkxpc3RfMTBfZGZfdHJhbnNwb3NlZF90aWJibGVfcGl2b3RfZ2VucmUKCiMgZHJvcCBjb2x1bW5zIHRvcE4sIHllYXIsIHVybApyaWJjZnRvcE5MaXN0XzEwX2RmX3RyYW5zcG9zZWRfdGliYmxlX3Bpdm90X2dlbnJlIDwtIHNlbGVjdChyaWJjZnRvcE5MaXN0XzEwX2RmX3RyYW5zcG9zZWRfdGliYmxlX3Bpdm90X2dlbnJlLCAtdG9wTiwgLXllYXIsIC11cmwsIC1pdGVtSUQpCnJpYmNmdG9wTkxpc3RfMTBfZGZfdHJhbnNwb3NlZF90aWJibGVfcGl2b3RfZ2VucmUKYGBgCgpgYGB7cn0KIyBwaXZvdCBsb25nZXIgZGF0YWZyYW1lCnJpYmNmdG9wTkxpc3RfMTBfZGZfdHJhbnNwb3NlZF90aWJibGVfcGl2b3RfZ2VucmUgJT4lIGdyb3VwX2J5KHRlc3RVc2VycykgJT4lCiAgc3VtbWFyaXNlKGFjcm9zcyhldmVyeXRoaW5nKCksIH4gc3VtKC4sIGlzLm5hKC4pLCAwKSkpCmBgYAoKCgojIyAxMC4zIEJlc3RpbW1lIHBybyBLdW5kZSBkZW4gQW50ZWlsIG5hY2ggR2VucmVzIHNlaW5lciBUb3AtRmlsbWUKKD1GaWxtZSBtaXQgYmVzdGVuIEJld2VydHVuZ2VuKSwKYGBge3J9CgpgYGAKCiMjIDEwLjQgVmVyZ2xlaWNoZSBwcm8gS3VuZGUgVG9wLUVtcGZlaGx1bmdlbiB2cyBUb3AtRmlsbWUgbmFjaCBHZW5yZXMsCmBgYHtyfQoKYGBgCgojIyAxMC41IERlZmluaWVyZSBlaW5lIFF1YWxpdMOkdHNtZXRyaWsgZsO8ciBUb3AtTiBMaXN0ZW4gdW5kIHRlc3RlIHNpZS4KYGBge3J9CgpgYGAKCg==